Computers and Reality - Cognitive Science 110 - Spring 2007

1. What is a Universal URM program? What is a Universal Turing Machine?
2. Why do we order the URM programs?
3. Order the following URM programs according to the convention from class:
   1. Programs with fewer symbols come before ones with more symbols.
   2. Programs with the same number of symbols are ordered lexicographically ("alphabetically"), according to the following ordering of the symbols: J S T Z 0 1 2 3 4 5 6 7 8 9 ( ) ,

   Q₁: J(1,1,1)  ;   Q₂: S(5)  ;   Q₃: S(1)S(2)  ;   Q₄: T(3,1)  ;   Q₅: S(1)Z(1)  ;   Q₆: S(12345)  ;   Q₇: Z(1)

4. Find each of the following programs: P₁₀; P₁₈; P₁₁₀₁ (where P_i denotes the i^th  program according to the ordering given above, starting with P₀ = "S(1)".).
5. What number gets assigned to the one-instruction program S(999)? (I.e., find n such that P_n = "S(999)".)
6. 1. Why do we have rule (i) at all? In other words, what would go wrong if we dropped it and decided to order URM programs using rule (ii) only?
   2. What, if anything, would go wrong if we kept rule (ii) as is but changed rule (i) to: "Programs with fewer instructions come before ones with more instructions"?
   3. When ordering words in the (English-English) dictionary, do we use "modified versions" of both rules (i) and (ii), or only one of them? If we use one of them only, explain why we don't need both. If we use both, explain why we need both.
   4. Optional: how about the numbering system libraries use for books? What conventions are used, and why?
7. What is the output of P₀ when given input = 5? What function does P₀ compute?
8. Give an n such that P_n computes the identity function f(x)=x.