Table of Contents

• Purpose
• Formal Definition
• Church's Thesis
• Alternative Computational Models
• Universal Turing Machine

• Purpose of this unit

  • The fundamental issue we will focus on for the remainder of this course are problems and problem solving methods or algorithms.

  • The purpose of this unit is to discuss the following ideas.

    1. The Turing machine model : A formal model for representing algorithms.

    2. Church's Thesis: This thesis states that any algorithm can be represented as a Turing machine.

    3. Universal Turing machines: A Turing machine which acts like a modern general purpose computer in that it can "run" other Turing machines and thus solve any problem which can be solved by Turing machines.

    4. Undecidability: A formal proof that natural, important problems such as the halting problem are "undecidable" or unsolvable.

• Formal Definition of a Turing Machine

  • M = (Q, , , q₀, , h)

    • Note I have added the halt state h as an extra element of the definition of a Turing machine.

    • I'm not going to cover here all the definitions as they are covered in the book, but please make sure you understand the following list of concepts related to a Turing machine.

      • What a configuration of a Turing machine is.

      • What the initial configuration of a Turing machine on an input string x is.

      • The fact that Turing machines can compute functions as well as decide/recognize languages.

      • The language accepted by a Turing machine (page 284).

      • The language decided by a Turing machine (page 294).

      • The difference between the two previous concepts of accepting a language and deciding a language.

• Church's Thesis

  • Church's Thesis states that any algorithm can be realized as a Turing machine.

  • That is, any algorithm which you implement using the C++ or Java programming languages can also be implemented using Turing machines.

  • The importance of this thesis is as follows:

    • First, we will prove that certain problems cannot be solved using Turing machines.

    • If Church's Thesis is true, this implies these same problems cannot be solved using any computer or any programming language we might ever develop.

    • Thus, in studying the fundamental capabilities and limitations of Turing machines, we are indeed studying the fundamental capabilities and limitations of any computational device we might ever construct.

  • Can Church's Thesis ever be proven correct?

    • Not really. To prove it correct, we would need to prove that for all possible models M of algorithms, any algorithm that can be represented in model M can also be represented as a Turing machine.

    • Instead, we will provide evidence that Church's Thesis is correct as described in the following section.

• Alternative computational models

  • In this section, we give evidence that Church's Thesis is correct by considering several alternate formal models of algorithms and show that they are equivalent to the Turing machine model.

  • The Basic Technique

    • We will formally define an alternative model AM
      • Possible example models include Turing machines with multiple tapes and C++ programs.

    • We will show that model AM is equivalent to our basic Turing machine model as follows:

      1. For every machine or program M₁ in model AM, there exists a Turing machine M such that L(M₁) = L(M).

      2. For every Turing machine M, there exists a machine or program M₁ in model AM such that L(M₁) = L(M).

    • We achieve the above two steps by employing constructive proofs very similar to examples we've seen before

      • Theorem 12.1 where we showed that any PDA which accepts by final state can be converted into a PDA which accepts by empty stack and accepts the same language.

      • Theorem 5.2 which shows that any NFA can be converted into an FA which accepts the same language.

    • Key point

      • Note in each case we are not creating a new machine from scratch.

      • Rather, we are modifying an existing machine in a different model to do essentially the same thing in our current model.

  • Example Summaries

    1. Turing machines with 2-tracks on their input tape

       • The basic idea is that to simulate a 2-track TM with an ordinary TM, we need a bigger tape alphabet.

    2. Turing machines with a 2-way infinite tape

       • Section 17.1.

       • The basic idea is to simulate a 2-way infinite tape TM with a 2-track TM by wrapping the "left end" of the tape onto the second track.

    3. Turing machines with multiple tapes (some fixed number n)

       • Section 17.2.

       • The basic idea is to simulate an n-tape TM with an n-track TM where track i holds the contents of tape i.

       • The cells for track i also need to mark where the tape head for tape i is located.

       • To simulate one move an n-tape TM, the n-track TM needs to

         1. Collect the tape head information from each track.
         2. Given this information and the current state, decide on how each track needs to be updated.
         3. Implement the update on each track.

       • Note each single transition of an n-tape TM requires many transitions from the normal TM.