4.1. Turing Machines

Turing machines for languages

---

Having looked at finite state computation and found it lacking, it makes sense to remove the memory restriction, and allow programs to use more memory on larger inputs.

How much more memory? Let's not restrict that in any way. A program can use as much memory as it wants. But it does need to stop, eventually, on every input.

It is not clear just what the memory should be like. You certainly cannot make an ad-hoc machine with infinitely many states. You would never finish.

For studying issues of computability, the exact nature of the memory is not really important. The key thing that we want is simplicity. A nice, simple model of computation is the Turing machine.

Chapter 3 of Sipser describes Turing machines in detail. Here, I only want to hit the high points.

Memory

The memory is a tape that can hold one symbol from a tape alphabet in each cell. The tape has a left end, but is infinite to the right.

        _______________________________
       | a | b | c | B | B | …
       |___|___|___|___|___|___________
         ^

Input

The input is written on the tape initially, starting at the left end. The input must be written using the input alphabet, which is a proper subset of the tape alphabet.

After the input are infinitely many blank symbols, where the blank symbol belongs to the tape alphabet but not the input alphabet. So the tape starts out looking like this, where B is the blank symbol:

  here is the inputBBBBBBBBBBBB…

Accessing the tape

There is a tape head that the program can move to the left and right. The program can read and write on the tape using the tape head. It can also move the tape head left or right.

Computation

There is a (finitely long) program that controls computation. The program can be described using states and transitions, where each transition is marked by actions to be taken.

But you can think of it as a program that can have a fixed number of variables that can hold one symbol each, where the program can use commands to read or write the tape or to move the head to the left or right.

Giving an answer

Some states (instructions) are designated as terminating states. Some of those are accepting states and some are rejecting states.

If M is a Turing machine then L(M) is the set of all strings s so that, when you run M on input s, M eventually stops and accepts s.

Turing machines for functions

---

A slightly different Turing model can be used to compute a function that takes a string and yields a string.

We just add a second tape, called the output tape. The machine writes its output on the output tape, followed by some special character that indicates the end of the output.

When the machine stops, its answer is written on the output tape.

I will refer to this kind of Turing machine as a functional Turing machine.

Turing computability

---

Say that

Language S is Turing computable if there exists a Turing machine M so that

1. M eventually stops on every input.

2. L(M) = S.

The function computed by a Turing machine

---

For any functional Turing machine M, define φ_M to be the partial function that M computes.

φ_M(s) = the output of M on input s, if M stops on input s.
φ_M(s) = ⊥ when M fails to stop on input s.

Let f:A* → B* be a total function. Say that

f is Turing computable is there exists a functional Turing machine M so that φ_M and f are the same function.

We will look later at computing partial functions. We say that partial function f is partially Turing computable if there exists a functional Turing machine M so that f = φ_M.