Turing Machines and Church-Turing Thesis in Theory of Computation

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

A turing machine is a mathematical model of a computation that defines an abstract machine. In this article, we learn about Turing machines, how they are defined formally and informally, and the Church-Turing thesis.

Table of contents.

Introduction.
Formal and informal definitions.
Multi-tape turing machines.
Formal definition of multi-tape turing machines.
The Church-Turing thesis.
Summary.
References.

Prerequisites.

Introduction.

In the prerequisite articles, we learned about regular and context-free languages. We learned of computational devices that accept or generate these languages and their limitations when it comes to languages such as; A = {ambncmn : m ≥ 0, n ≥ 0}.

A turing machine models a real computer. These machines accept all context-free grammar as well as languages such as A.

In this article, we will try to prove that "every problem solvable by a real computer is solvable by a turing machine" - this is the church turing thesis.

Formal and informal definitions.

A turing machine will consist of the following;

First we have k tapes, each tape divided into cells. This tape is infinite on both sides left and right. Each cell in the tape stores a symbol that belongs to a finite set T referred to as the tape alphabet. This alphabet has a blank symbol ⋄ If a cell has this symbol, it is considered empty.

Let's look at an example of a turing machine where k is 2;

Each tape has a tape that can be moved along the other tape. It only moves a single cell per move. It reads the cell it is currently positioned at and replaces the symbol in the cell with another symbol.
There is also a state control that can be any of a finite number of states. A finite set of states is denoted by Q, this set has three special states namely, start, accept, and reject.

During a single step of computation the turing machine does the following;

At the beginning it is in a state r of Q and each k tape head is on a specific cell.
Depending on the current state r and k symbols;

The machine switches to state r' of Q
Each tape head writes a symbol T in the cell it is currently scanning.
Each tape head can move one cell to the left, right, or stay where it currently is.

A formal definition.

A deterministic turing machine is 7-tuple consisting of M = (Σ, Γ, Q, δ, q, qaccept, qreject).
Where;

Σ is a finite set referred to as an input alphabet.
Γ is a finite set referred to as a tape alphabet, it has the blank symbol ⋄ and Σ ⊆ Γ.
Q is a finite set whose elements are referred to as states.
q is an element of Q referred to as the start state.
qaccept is an element of Q, it is referred to as the accept state.
qreject is also an element of Q, it is referred to as the reject state.
δ is referred to as a transition function.
δ:Q × Γk→ Q × Γk × {L, R, N}k.
This function is a program of the turing machine, it tells the machine what it can do in one computation step.

Multi-tape turing machines.

These machines have multiple tapes each accessed with a separate head that moves independently despite the other heads.

In the beginning, the input is at tape 1 while others remain blank. In the next step, the machine reads consecutive symbols under its head and prints a symbol on each tape then moves its head.

Although it is easier to obtain a two-tape machine compared to a single-tape turing machine, this doesn't mean that a two-tape machine is more powerful.

A formal definition of multi-tape turing machines.

This machine is 6-tuple (Q, X, B, δ, q0, F) where;

Q is a finite set of states.
X is the tape alphabet.
B is the blank symbol.
δ is a relation between states and symbols where;
δ: Q × Xk → Q × (X × {Leftshift, Rightshift, Noshift })k where there is k number of tapes.
q0 is the initial state.
F is the set of final states.

Note that for every multi-tape turing machine, there is an equivalent single-tape turing machine.

The Church-Turing thesis.

An algorithm is a list of steps describing how to solve a problem with a computer and therefore any computational process that can be specified by a program is considered an algorithm.

Similarly, a turing machine specifies a computational process and therefore we consider it as an algorithm.

Now, we ask. Is it possible to give a mathematical definition of an algorithm?
Having stated that every program be it a java program or C program represents an algorithm and that every turing machine represents an algorithm. We ask ourselves, are these two statements regarding an algorithm equivalent?

The answer is yes, it also implies that many different notions of computational processes are equivalent.

For example, the following are computational models.

One-tape turing machines.
Non-deterministic turing machines.
k-tape turing machines where k >= 1.
Java, C++ programs.

Any of the models can be converted to any other model.

The Church-Turing thesis: It states that every computational process that is intuitively considered an algorithm can be converted to a turing machine.
In other terms, we define an algorithm to be a turing machine.

Summary.

A turing machine is a mathematical model of a computation that defines an abstract machine. Despite its simplicity, given any algorithm, this machine is capable of implementing the algorithm's logic.

The Church-Turing thesis states that every computational process that is said to be an algorithm can be implemented by a turing machine.

References.

Variations of turing machines