Study Questions Logic III Exam 1, Spring 09

I. Enumerability

0. What is a function? What is the domain and range of a function?

1. What does it mean to say that a set is enumerable? Give a definition using the notion of a function. What adjustments to the definition are needed to make sure that finite sets are enumerable? Give three distinct ways of making the correction.

2. Prove that the set of all positive and negative integers is enumerable.

3. Prove that the set of rational numbers is enumerable.

4. Is the set of all (finite) n-tuples of natural numbers enumerable, where the n-tuples can be any length? Prove your answer.

5. Suppose I have a set that can be divided into finitely many infinite sets, each of which can be enumerated. Can the whole set be enumerated? Explain your answer.

6. Suppose I have a set that can be divided into (enumerably) infinitely many finite sets such that those finite sets can be enumerated. Can the whole set be enumerated? Explain.

7. Explain the alphabetic ordering method for demonstrating that a set is enumerable. Illustrate the method by working through an example.

8. Prove that some set is infinite but not enumerable.

9. Consider the set of all infinite lists of natural numbers. Is it enumerable? Prove your answer.

10. The philosopher Bertrand Russell once considered a barber who shaved everyone who doesn't shave himself. Consider the formula that expresses this feature of the barber b in predicate logic: Âx(Sbx Ç ~Sxx). What does this formula have to do with our course?

11. Cantor's Theorem says that the set of real numbers is infinite but not enumerable. Prove Cantor's Theorem.

12. Prove that the set of all functions from N into N is not enumerable, where N is the set of natural numbers.

13. Suppose you have a language with finitely many symbols, whose formulas describe functions of mathematics. For example the language might be arithmetic which contains such symbols as +, *, -, /, <, >, =, 0, and symbols for predicate logic. One of the functions that this language can define is squaring. Presuming the domain of the quantifiers is the natural numbers, here is the definition of the squaring function s: s(x)=x*x. There are many other interesting functions that this language can define. Prove that there are functions that this language cannot define.

14. Explain techniques you can use to prove that a) a set is enumerable, and b) a set is not enumerable. Consider the set of all finite symbol strings written in some denumerably infinite alphabet. Suppose somebody tries to use the diagonal method to prove (incorrectly of course) that this set is not enumerable. Why does the reasoning of the diagonal method fail in this case?

II. Turing Computation

1. Prove that the set of all Turing Machines is enumerable. Why does it follow immediately that there are functions that no Turing machine can compute?

2. Prove Turing's Theorem.

3. What does it mean to say that a function is computed by a Turing Machine?

4. In class, I claimed that every Turing machine computes some function or other. But a Turing machine might go into an infinite loop and so not complete a computation. Explain why I was nevertheless right.

5. In the proof we gave of Turing's Theorem, we constructed a machine named K by putting a copy routine on the front and a "ditherer" on the back of a purported machine H that could compute the halting function. Why were these additions made? Relate your answer to the diagonal strategy for proving that certain sets are not enumerable.

6. In the proof of Turing's Theorem we showed that machine K has the feature that K halts given n on the tape iff the Turing machine with number n does not halt given n is on the tape. Show that the assumption that such a machine K exists leads to a contradiction.

7. Let function a be defined so that a(n) is 2 if Tn(n)=? and a(n)=? otherwise, where Tn(n)=? means the nth Turing machine in our enumeration does not a compute an answer given n ones on the tape. Prove that no Turing machine can compute a.

8. Suppose we have proven that function a described in the previous question is not Turing computable. Use this to prove that the halting function is not Turing computable.

III. Abacus Computation

1. What is Turing's Thesis? Why is it called a thesis rather than a theorem? What evidence supports the thesis? How was abacus computation used in our class to help support Turing's Thesis? What other method has been used to provide evidence for the thesis?

2. Design an abacus that computes the even-odd function p. That is, when i is even, p(i)=0 and when i is odd p(i) is 1. Assume the input number is in register n and that the answer is also in register n.

3. What are the capabilities of an abacus that might make one think that abacus computation is more powerful than Turing computation? Explain briefly why the abilities of an abacus can be simulated by a Turing machine after all.

4. What reasons do we have for thinking that any effective computation at all can be completed by an abacus?

5. Explain how the contents of the registers of an abacus can be represented using the Turing machine's tape. Why was it necessary to use a representation where the number n is represented by n+1 strokes on the tape?

6. Why was it necessary to use two different ways of representing zero when simulating an abacus with a Turing Machine?

7. What is the mop-up graph and why is it needed?

8. Explain in English how the Turing machines for the commands n+ and n- are constructed. Just explain the sequence of events on the tape for these commands.

9. What is a recursive solution to a problem? Give an example, making use of strategies presented in class for solving the addition problem with a Turing machine.

10. Give reasons for thinking that every computation performed by a modern computer can be performed by an abacus. Why would showing this be important.