Philosophy of Computer Science: Online Resources

Position Paper #3:
Comments on Determining Validity

Last Update: Sunday, 27 March 2022 — 1:15 pm

It's one thing to say that you think that an argument is valid. It's another to say why you think so. Just saying that it "seems logical" isn't enough.

There are several ways to convince your reader that an argument is valid. I'll list a few, and then apply some of them to Position Paper 3.

First, you can try to convince your reader that if the world had made the premises true, then the world would have to have made the conclusion true, that is, that the conclusion would have to be true if the premises were true. If you think that the argument is invalid, then you have a slightly easier task: Find a situation in which the premises are true but in which the conclusion is false.

Second, you could show that the argument follows a generally accepted rule of inference, like Modus Ponens:

or a rule that generalizes this:

or a set-theoretic version:

Third, you can reason with the premises. Let me illustrate this with the argument of Position Paper 3:

  1. A physical object can compute iff it can do what a Universal Turing Machine can do.

  2. A computer is (by definition) any physical device that can compute.

  3. The human brain is a physical object that can do what a Universal Turing Machine can do.

  4. Therefore, the human brain is a computer.

This is valid (but if a student argues that it is invalid and gives a counterexample to show that 1, 2, 3 could be true while 4 was false, they should get full credit).

Here's why it's valid: Premise 1 says that a physical object, x, can compute iff x can do what a Universal Turing Machine can do. And Premise 2 says that a thing, x, is a computer iff x is a physical device that can compute. We can logically combine these to get:

(If A is true iff B is true, and if B is true iff C is true, then A is true iff C is true—just eliminate the "middleman".) Call this "intermediate conclusion" Premise 2.5.

(Some students might point out that this requires a missing premise to the effect that "device" = "object". If you believe that equality, then the argument so far is valid. If you don't believe it, then the argument may still be valid, but will be unsound. For the sake of this example, let's assume that "device" = "object".)

Premise 3 says that the human brain is a physical object that can do what a Universal Turing Machine can do. Combining Premises 2.5 and 3, we get:

But that's Conclusion 4. We've just shown that the conclusion is true relative to the truth of the premises, so the argument 1,2,3 ⊢ 4 is valid. (On the use of the "⊢" symbol, see §2.5.1 of the book.)

Now consider the argument 1,2,5 ⊢ 6. Premise 5 says that a Universal Turing Machine can execute ("do") MS Word. We can combine this with Premise 2.5 to get:

That's Conclusion 6. So, we've just shown why 1,2,5 ⊢ 6 is valid.

Finally, consider 4,6 ⊢ 7: We can combine Conclusions 4 and 6 to get:

That's why 4,6 ⊢ 7 is valid.

Digression on Universal Turing Machines:

Some students might not be clear about the relationship between Turing Machines and Universal Turing Machines. Although all Universal Turing Machines are Turing Machines, most Turing Machines are not Universal Turing Machines.

A Turing Machine computes exactly one algorithm; it is a hardwired computer capable of doing only one thing.

A Universal Turing Machine is a stored-program, general-purpose computer. If you give it a suitable program, it can execute that program, so it can do what any other Turing Machine can do (if given that Turing Machine's program).

Your laptop is a physical implementation of a Universal Turing Machine. You can program it, or load programs into it, that will allow it to do any computable task. If you run out of memory, you can buy some more. (Unfortunately, if you run out of time, you can't buy more time!) And contrary to what many students might think, your laptop does have a "tape"; it's called "random access memory" (RAM), and it's somewhat more flexible than a Turing Machine "tape", but it plays the same role as the tape. More precisely, the combination of the memory in the hard drive plus RAM corresponds to the tape.

Digression on Implementing Microsoft Word:

Some students might confuse 'do not' with 'cannot'. Just because you have a computer that does not run Microsoft Word doesn't mean that your computer cannot run it. As counterexamples to the statement that "any computer can execute Microsoft Word", some students might suggest:

There are problems with all of these. First, what kind of calculator? If it's a non-programmable one, then it's not a Universal Turing Machine, and we wouldn't consider it a "computer" for the sake of this argument. If it's programmable, and if it's Turing-Machine–equivalent—that is, if it can, in principle, compute anything that a Turing Machine can compute—then, given enough memory, it could run Microsoft Word. The same goes for iPhones (for which, in fact, a version of Microsoft Word is available in the App Store). I don't know if there's a version of Microsoft Word for Linux machines, but that doesn't mean that there couldn't be. For one thing, the operating system (Linux) is irrelevant; all that counts is the CPU: If Microsoft Word's algorithm could be compiled into the Linux machine's machine language, then the Linux machine could run Microsoft Word.

And—some Windows students may be surprised to learn—Macs can run Microsoft Word! I use it frequently on my Mac. (And the MacOS operating system, just like Linux, is a version of the Unix operating system, so that's not the stumbling block for Linux.) Moreover, many years ago, I was able to run the very same Microsoft Word program on my old PowerPC Mac and on my newer Intel Mac, so even the machine language is somewhat irrelevant, as long as there's a way to compile the algorithm into it.

Copyright © 2022 by William J. Rapaport (rapaport@buffalo.edu)
http://www.cse.buffalo.edu/~rapaport/OR/pp3comments.html-20220327