What is a Turing machine?

In the computational world, the Turing machine is a powerful computation engine. The invention of the Turing Machine is done by Alan Turing in 1936. A Turing Machine (TM) is a diagrammatic model of a fictional computer. It determines an output from a set of input variables using a pre-defined set of rules. It is used to get around the limitations of finite automata and pushdown automata.

The Turing machine is represented with the help of the following seven components. It is shown in a tuple:

TM = ( $\zeta$,Q, $q_0$, $\sum _{}^{}$, F,  $\delta$, B), where

$\zeta$: The tape symbols

Q: A limited number of input states

_{$q_0$:} The starting point 

$\sum _{}^{}$: The input symbol's finite set

F: A set of final states (outcomes)

$\delta$: A mapping function or transition function

 $\delta :Q*\zeta \to Q*\zeta *\left(L,R\right)$ is a computation transition function, where Q represents the input state, $\zeta$ is the symbol present in the tape and $\left(L,R\right)$ represents the $L$ left and $R$ right move.

B is a blank symbol used as an end marker in the tape T.

The Turing machine consists of an infinitely long tape whose ends are filled with a blank symbol B. This tape work like a memory or data storage in the computation. The read/write operation is performed on the Turing machine tape. For this, it has a read/write head (R/W head) to perform the read/write operation.

This tape consists of infinite cells where each cell holds either input symbol or blank space (special symbol). It also has a head pointer. The head pointer points to the cell presently being read. It can move in both directions namely left and right. The figure shows a Turing machine with only one tape. Multi-tape Turing machines are another sort of Turing machine. Every multi-tape Turing Machine has a single-tape Turing Machine counterpart.

Type-0 Grammar

In computational geometry, there are many types of grammar. But the type-0 grammar is accepted by the Turing machine.

Type-0 grammar is known by various names such as Recursively Enumerable Grammar (REG), Unrestricted grammar, and phase structure grammar. If the input string does not belong to the language, then the TM repeatedly loops within certain states without reaching the end state.

Quadruple for type-0 grammar is: $G=\left(\sum _{}^{},V_n, P, S\right)$

 where:

• $\sum _{}^{}$represents the finite (limited) set of terminals (small case letter)
• $V_n$ represents finite (limited) non-empty set of non-terminals (uppercase letter)
• P represents finite non-empty set of production rule
• S represents the start symbol

The production rule for type-0 grammar is:

$\alpha \to \beta$, here $\alpha$ is non-terminal and $\beta$ is terminal.

$\alpha \to {\left(\sum _{}^{}\cup V_n\right)}^{*}{V}_n{\left(\sum _{}^{}\cup V_n\right)}^{*}$

$\beta \to {\left(\sum _{}^{}\cup V_n\right)}^{*}$

What is the Halting Problem?

In order understand the halting problem, it is very important to know the following terminologies.

Language Decidability

• When a Turing machine accepts and stops (halt) on each input string w, the language is referred to as recursive or decidable.
• Every decidable language is Turing-Acceptable.

Language

• If L is a language and it is decidable, then the complement of L (L’) is also decidable.
• For a decidable language, an enumerator has existed.

Decidable problem

• If a problem P is solved by the algorithm in a finite amount of time, then this problem is called decidable.
• But sometimes there exists specific problems that are not solved by the algorithms. These problems are unsolvable.
• In a decidable problem, P is a decision problem. P is decidable, if the language L created by the problem P has all yes instances.
• The Turing machine halts in either accept or reject state for each decision language on each input string. This is depicted in the diagram below:-

Example 1:

Check whether the issue is decidable or not.

“Is there a palindrome in the number?”

Solution

• A palindrome is a number that remains the same when its digits are reversed. Example- {3663, 21212, 75357...}
• Reverse the number and match it with the original number. If the reversed number is the same as an original number, then it is called a palindrome number.
• If the number is a palindrome, then the output is ‘yes’ and this is an accepted state. Otherwise, the output is ‘no’ which shows the rejected state. Thus, it gives a binary output either ‘yes’ or ‘no’.
• As a result, this is a decidable problem.

Example 2:

A regular language L is given and w is an input string. Check whether the input string w belongs to L or not.

Solution

Take the DFA that accepts the regular language L. Check whether the input string w obeys the grammar. If $w\in L$ , then it is accepted and if $w\notin L$, then it is rejected.

Undecidable languages

• A language is said to be undecidable, if the language L among all yes occurrences to P can't be decided.
• A language that is undecidable is not a recursive language. It could however be a recursive enumerated language in some instances.
• There is no Turing machine that receives an undecidable language and makes a decision for each of the input strings.

Undecidable language creates the halting problem. Turing machine works like a computer CPU. It controls all the data manipulations.

Halting state

• Halt state: Halt state is either Accept state or Reject state.

The output of the Turing machine can be a Halt or No Halt.

• Halt: The machine will reach a halt state (Accept/Reject state) after a predetermined number of states.

• No Halt: The machine will never come to a complete halt (Accept/Reject). In this case, the machine will run continuously.

Whether Halting Problem is undecidable?

Will a program/algorithm ever come to a halt? The term "halting" refers to whether an algorithm or program will accept or reject a given input and then halt. It indicates that it would never become stuck in an endless loop.

Let us prove that the halting problem is undecidable.

Assume that there exists a Turing machine S that decides H. Consider another Turing machine T which can be defined as follows: It takes an input <a> executes S on input <a,<a>> and halts if and only if S rejects. In other words, T takes the input program a, executes the Turing machine that decides the halting problem on the input "program a, on input a". Based on the result, if it says "yes, a on input <a>, it halts", then it loops repetitively. Otherwise, if it results in "no, a on input <a>, it does not halt", then it terminates. The notation <a> is the transformation of program a on a particular input and therefore, it can be passed as input to another program.

If T receives <T> as input, then it executes S on input <T,<T>>. It will result in the following two cases.

• S accepts. It indicates that T on input <T> halts. According to the definition of T, if S accepts then it enters an infinite loop and therefore, T on input <T> must not halt.
• S rejects. It indicates that T on input <T> does not halt. According to the definition of T, if S rejects then it must be terminated and therefore, T on input <T> halts.

The preceding argument results in a contradiction. The contradiction happens due to the incorrect assumption on the existence of S. Its existence resulted in the existence of T which has an incorrect behaviour. Therefore, our assumption of S is wrong. In other words, there do not exists S that decides H.

As a result, the halting problem is unsolvable.

Common Mistakes

• Generally, students are confused about undecidability. Undecidability is a state when a Turing machine does not make any decision about input string w of the language L. Turing machine only accepts the decidable language.
• The Turing machine's halting problem occurs when the machine does not achieve its final state (Halt state). The halting problem is generated when more than two comparisons are available in the computation.
• The computation of the Turing machine is deterministic when a set of rules impose at most one action to be performed for any given situation. A non-deterministic Turing machine's computation is a tree of configurations that can be achieved from the starting configuration.

Context and Applications

This topic is helpful for the graduation, master and examination, especially for

• Bachelors in Computer Science and Engineering
• Bachelors in Information Processing
• Masters in Advanced Automata Theory

Related concepts

• Finite Automata
• Variations of Turing machine
• Grammar in Automata

Practice Problems

Q1- The Halting problem is ____________ over Turing machines.

1. Decidable
2. Undecidable
3. Both
4. None

Answer: 2. Undecidable

Explanation- The halting issue is undecidable. That is, for every program and input, there is no algorithm that solves the halting problem.

Q2- How many elements Turing machine consists of?

1. 3
2. 5
3. 7
4. 9

Answer: 3. 7

Explanation- A Turing machine consists of 7 element.

Q3- What is the transition function of the Turing Machine?

1. $\delta :Q*\zeta \to Q*\zeta *\left(L,R\right)$
2. $\delta :Q*\zeta \to Q*\zeta *\left(L,L\right)$
3. $\delta :Q·\zeta \to Q*\zeta *\left(L,R\right)$
4. None

Answer- 2. $\delta :Q*\zeta \to Q*\zeta *\left(L,R\right)$

Explanation- $\delta :Q*\zeta \to Q*\zeta *\left(L,R\right)$ is a computation transition function. Where Q represents the state. $\zeta$ is the symbol present in the tape. $\left(L,R\right)$ is the left and right move.

Q4- Which language is not accepted by the Turing machine?

1. Recursive enumerable
2. Recursive
3. None of the mentioned
4. Language can be enumerated by some TM

Answer: 2. Recursive

Explanation- Even if all languages are recursively enumerable, the Turing computer accepts them all. The terms recursive and enumerable refer to the same set of rules being repeated an unlimited number of times.

Q5- Y is a simple mathematical model of a computer and it has unlimited memory. Y is a finite automaton with a read/write head. Y has an infinite tape divided into cells where each cell holds one symbol. What is Y?

1. Push Down Automata
2. Turing Machine
3. Definite Finite Automata
4. None

Answer: 2. Turing Machine

Explanation- Here, Y denotes the Turing machine. It is the mathematical model with read/write head.