Basics of Computability - Formal Definition of a Turing Machine - C3

5-minute read

Turing Machines - Formal definition

A Turing machine $M$ is a sextuple ($\mathcal{Q},{q_0},F,\Sigma,\Gamma,\delta)$

  • $\mathcal{Q}$ is the finite set of all states.

  • ${q_0}$ is the initial state. ${q_0} \in \mathcal{Q} $

  • $F$ are the final states. This is the collection of halt/accept states and halt/reject states ${F} \in \mathcal{Q}$

  • $\Gamma$ is the input alphabet. We denote the blank symbol as $\wedge$ and require that $\wedge \notin \Gamma$

  • $\Sigma$ is the tape alphabet. We note that $\Gamma \subseteq \Sigma$ and $\wedge \in \Sigma$.

  • $\delta:(Q/F)$ x $(\Sigma) \mapsto Q$ x $\Sigma$ x $\{L,R\}$

This point describes a function delta which serves the purpose of our transition logic.

The input to the function will be a state and a tape alphabet. However, note that the state cannot be a final state $Q/F$. This function is therefore not defined for final states. This is because once we are on a final state, the Turing machine has halted.

Upon seeing the current state and alphabet pair, the function tells the Turing machine to do 3 things:

  • Change the state of the Turing machine to a new state.
  • Write down a letter over the current symbol that you are reading.
  • Either move left or right of the tape.

The act of writing nothing can be simulated by writing the same symbol to the tape that was read.

The act of moving nowhere can be simulated in two steps' move to the Left in one step and then move to the right in another step.

On Halting

From our definition, it may not be clear as to how the machine will determine when it halts and succeeds, and when it halts and rejects. The key insight is that the transition function does not take as input any of the final states.

Let us imagine the Turing machine has changed to a state in F. Since the transition function $\delta$ is not defined for states in $F$ , the Turing machine cannot move and will halt.

Recall that $F$ consists of two groups of states halt/succeed and halt/reject, without loss of generality, we will assume that when the Turing machine halts on a state, it will be able to distinguish between the two.

Turing Machines vs A Turing Machine

One distinction we need to make is that of a single Turing machine and Turing machines.

Turing machines in general can be described using the formal definition stated above.

Let us imagine that we wrote down a specific configuration for our tuples, i.e. we wrote down all the possible states, a transition function and all of the final states. This would be a description of a specific Turing machine. Let’s call this specific instantiation, M1. According to the Church-Turing thesis, M1 implements an algorithm. A specific algorithm and only one.

Recall that Turing machines in general implement algorithms, if we configure a specific Turing machine, it will implement a specific algorithm. Moreover, since one algorithm usually solves one problem, our specific instantiation of A, solves exactly one problem.

Hmm: Something is not adding up. If a Turing Machine implements one algorithm. How comes my laptop can implement many algorithms? This is somewhat out of scope, but to answer succintly, there is an algorithm $A_1$ which takes as input any other algorithm $A_n$, along with that algorithms input $I_n$ and simulating $A_n(I_n)$ . The corresponding Turing Machine is called a Universal Turing Machine.

On Looping

We have dived into the details of what happens when a Turing machine halts, however a Turing machine can also loop forever.

Intuitively, if you wrote a for loop in a programming language that did not have a termination condition, it would loop forever or until you had nomore memory.

A natural question that arises, is whether we can tell whether an arbitrary Turing machine halts. If my explanation has been lacking so far and so you have not absorbed the notion of Turing machine, this question can also be rephrased as:

Can we tell whether an arbitrary program will stop?

In the case of a for loop that does not have a terminating condition, this is easy. However, we want an algorithm that can tell whether an arbitrary program will halt.

Now that we have a formal definition of a Turing machine which can solve all problems we believe are solvable. If we show that no Turing machine can decide whether an arbitrary program will halt, by the Church-Turing thesis, we show that no algorithm exists to do this and that the problem is un-solveable. This is the power of our formal definition!

For context, this problem is known as the halting problem. A simplified and informal proof follows:

  • Given an arbitrary program, we run the program and wait for it to halt.

  • Assuming 10 years have passed and the program has not halted. We cannot yet assume that the program will never halt, as there is the possibility that it will halt after 10 years and 1 second.

  • Assuming 20 years have passed and the program has not halted. Still we cannot assume that the program may never halt. Maybe it was going to halt after 20 years and 1 second.

  • Given N seconds where N is large but finite, we cannot assume that the Turing machine will not halt, as it could halt at the N+1’th second.

One intricacy to our simple proof, is that we assume that our program will run in finite time and that the person simulating this program is also operating in finite time. If the simulator could wait an infinite amount of time, then he could solve the halting problem, but only for programs that run in a finite amount of time. The halting problem for programs that run in an infinite amount of time, will still be un-computable.

This is a small throw-away point and if not understood, will hold no relevance in further reading.