The Church-Turing Thesis

Return to List of Lectures

Previous Lecture

• Misc
  • Hour exam 2
    • Wednesday after break (March 23)
    • Material since 1st hour exam (e.g., PDAs, CFGs, their equivalence, non-context-free languages, Turing machines, etc.)
    • Otherwise similar rules and format to 1st exam, especially open references
• Questions?
• The Church-Turing Thesis
  • Section 3.3
    • Church-Turing thesis: Intuitive notion of algorithm equivalent to Turing machine
      • In fact, all models that seem to capture the intuitive notion of algorithm are equivalent to each other
    • Turing machine descriptions can be high-level algorithms instead of states and tape moves
    • Turing machines have to read strings
      • Every input has to be expressed as string
      • ⟨O⟩ = string expression for object O
    • Example with graph
  • Discussion and consequences
    • Henceforth we’ll mostly use pseudocode for algorithms, and Turing machines will appear mainly when we want a simple way of representing a computation, e.g., so another computation can do something with it
      • For example, an algorithm to interpret a Turing machine, i.e., do the same thing as that machine on a given input
        

        interpret( ⟨M⟩, w )
            (⟨M⟩ = list of states, transition function as table indexed by state and tape symbol)
            tape = [ w  ]
            tapePos = 1
            state = q0
            while state ≠ qaccept and state ≠ qreject
                nextState, symbol, dir = M.transitions( state, tape(tapePos) )
                state = nextState
                tape(tapePos) = symbol
                if direction = 'L'
                    tapePos = tapePos - 1
                else
                    tapePos = tapePos + 1
            end while

      • Since this algorithm exists, therefore “universal Turing machine,” a Turing machine that can simulate any other, exists
      • …and programming languages interpreters exist for all pairs of languages and/or abstract algorithms
      • …and physical computers are universal
    • Can computers/algorithms/programs compute on ℜ (set of reals)?
      • No enumerator can enumerate all of ℜ (diagonalization)
      • Number of strings is countable
        • Therefore number of algorithms is countable, since we saw with the universal interpreter above that every Turing machine = every algorithm can be encoded as a string
        • But the number of functions is uncountable
        • Therefore most things aren’t computable
    • Can we have nondeterminism in real programming languages?
      • We can at least simulate it, because we saw that a deterministic Turing machine could simulate a nondeterministic one
• Next
  • Introduction to (un)decidability
  • Read section 4.1

Next Lecture