Undecidable Problem about Turing Machine

The reduction is used to prove whether given language is desirable or not. In this section, we will understand the concept of reduction first and then we will see an important theorem in this regard.

Reduction

Reduction is a technique in which if a problem P1 is reduced to a problem P2 then any solution of P2 solves P1. In general, if we have an algorithm to convert an instance of a problem P1 to an instance of a problem P2 that have the same answer then it is called as P1 reduced P2. Hence if P1 is not recursive then P2 is also not recursive. Similarly, if P1 is not recursively enumerable then P2 also is not recursively enumerable.

Theorem: if P1 is reduced to P2 then

1. If P1 is undecidable, then P2 is also undecidable.
2. If P1 is non-RE, then P2 is also non-RE.

Proof:

1. Consider an instance w of P1. Then construct an algorithm such that the algorithm takes instance w as input and converts it into another instance x of P2. Then apply that algorithm to check whether x is in P2. If the algorithm answer 'yes' then that means x is in P2, similarly we can also say that w is in P1. Since we have obtained P2 after reduction of P1. Similarly if algorithm answer 'no' then x is not in P2, that also means w is not in P1. This proves that if P1 is undecidable, then P1 is also undecidable.
2. We assume that P1 is non-RE but P2 is RE. Now construct an algorithm to reduce P1 to P2, but by this algorithm, P2 will be recognized. That means there will be a Turing machine that says 'yes' if the input is P2 but may or may not halt for the input which is not in P2. As we know that one can convert an instance of w in P1 to an instance x in P2. Then apply a TM to check whether x is in P2. If x is accepted that also means w is accepted. This procedure describes a TM whose language is P1 if w is in P1 then x is also in P2 and if w is not in P1 then x is also not in P2. This proves that if P1 is non-RE then P2 is also non-RE.

Empty and non empty languages:

There are two types of languages empty and non empty language. L_et L_e denotes an empty language, and L_ne denotes non empty language. L_et w be a binary string, and Mi be a TM. If L(M_j) = Ф then Mi does not accept input then w is in L_e. Similarly, if L(M_j) is not the empty language, then w is in L_ne. Thus we can say that

L_e = {M | L(M) = Ф}
L_ne = {M | L(M) ≠ Ф}

Both L_e and L_ne are the complement of one another.

Introduction to Undecidability

In the theory of computation, we often come across such problems that are answered either 'yes' or 'no'. The class of problems which can be answered as 'yes' are called solvable or decidable. Otherwise, the class of problems is said to be unsolvable or undecidable.

Undecidability of Universal Languages:

The universal language L_u is a recursively enumerable language and we have to prove that it is undecidable (non-recursive).

Theorem: L_u is RE but not recursive.

Proof: Consider that language L_u is recursively enumerable language. We will assume that L_u is recursive. Then the complement of L_u that is L`u is also recursive. However, if we have a TM M to accept L`u then we can construct a TM L_d. But L_d the diagonalization language is not RE. Thus our assumption that L_u is recursive is wrong (not RE means not recursive). Hence we can say that L_u is RE but not recursive. The construction of M for L_d is as shown in the following diagram:

Post Correspondence Problem

In this section, we will discuss the undecidability of string and not of Turing machines. The undecidability of the string is determined with the help of Post's Correspondence Problem (PCP). Let us define the PCP.

"The Post's correspondence problem consists of two lists of string that are of equal length over the input. The two lists are A = w₁, w₂, w₃, .... , w_n and B = x₁, x₂, x₃, .... x_n then there exists a non empty set of integers i₁, i₂, i₃, .... , in such that,
w₁, w₂, w₃, .... w_n = x₁, x₂, x₃, .... x_n"

To solve the post correspondence problem we try all the combinations of i₁, i₂, i₃, .... , in to find the w1 = x1 then we say that PCP has a solution.

Example 1:

Consider the correspondence system as given below

A = (b, bab³, ba) and B = (b³, ba, a). The input set is ∑ = {0, 1}. Find the solution.

Solution:

A solution is 2, 1, 1, 3. That means w₂w₁w₁w₃ = x₂x₁x₁x₃

The constructed string from both lists is bab³b³a.

Example 2:

Does PCP with two lists x = (b, a, aba, bb) and y = (ba, ba, ab, b) have a solution?

Solution: Now we have to find out such a sequence that strings formed by x and y are identical. Such a sequence is 1, 2, 1, 3, 3, 4. Hence from x and y list

Example 3:

Obtain the solution for the following system of posts correspondence problem. A = {100, 0, 1}, B = {1, 100, 00}

Solution: Consider the sequence 1, 3, 2. The string obtained from A = babababb. The string obtained from B = bababbbb. These two strings are not equal. Thus if we try various combination from both the sets to find the unique sequence, we could not get such a sequence. Hence there is no solution for this system.

Example 4:

Obtain the solution for the following system of posts correspondence problem, X = {100, 0, 1}, Y = {1, 100, 00}.

Solution: The solution is 1, 3, 1, 1, 3, 2, 2. The string is

X1X3X1X1X3X2X2 = 100 + 1 + 100 + 100 + 1 + 0 + 0 = 1001100100100
Y1Y3Y1Y1Y3Y2Y2 = 1 + 00 + 1 + 1 + 00 + 100 + 100 = 1001100100100

Halting Problem

Note:- To understand better the halting problem, we must know Decidability, Undecidability and Turing machine, decision problems and also a theory named as Computability theory and Computational complexity theory.

Some important terms:

• Computability theory –
  The branch of theory of computation that studies which problems are computationally solvable using different model. In computer science, the computational complexity, or simply complexity of an algorithm is the amount of resources required for running it.
• Decision problems –
  A decision problem has only two possible outputs (yes or no) on any input. In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values. Like is there any solution to a particular problem? The answer would be either a yes or no. A decision problem is any arbitrary yes/no question on an infinite set of inputs.
• Turing machine –
  A Turing machine is a mathematical model of computation. A Turing machine is a general example of a CPU that controls all data manipulation done by a computer. Turing machine can be halting as well as non halting and it depends on algorithm and input associated with the algorithm.

Now, lets discuss Halting problem:

The Halting problem – Given a program/algorithm will ever halt or not?

Halting means that the program on certain input will accept it and halt or reject it and halt and it would never go into an infinite loop. Basically halting means terminating. So can we have an algorithm that will tell that the given program will halt or not. In terms of Turing machine, will it terminate when run on some machine with some particular given input string.

The answer is no we cannot design a generalized algorithm which can appropriately say that given a program will ever halt or not?

The only way is to run the program and check whether it halts or not.

We can refrain the halting problem question in such a way also: Given a program written in some programming language(c/c++/java) will it ever get into an infinite loop(loop never stops) or will it always terminate(halt)?

This is an undecidable problem because we cannot have an algorithm which will tell us whether a given program will halt or not in a generalized way i.e by having specific program/algorithm.In general we can’t always know that’s why we can’t have a general algorithm.The best possible way is to run the program and see whether it halts or not.In this way for many programs we can see that it will sometimes loop and always halt.

Proof by Contradiction –

Problem statement: Can we design a machine which if given a program can find out if that program will always halt or not halt on a particular input?

Solution: Let us assume that we can design that kind of machine called as HM(P, I) where HM is the machine/program, P is the program and I is the input. On taking input the both arguments the machine HM will tell that the program P either halts or not.

If we can design such a program this allows us to write another program we call this program CM(X) where X is any program(taken as argument) and according to the definition of the program CM(X) shown in the figure.

In the program CM(X) we call the function HM(X), which we have already defined and to HM() we pass the arguments (X, X), according to the definition of HM() it can take two arguments i.e one is program and another is the input.Now in the second program we pass X as a program and X as input to the function HM().We know that the program HM() gives two output either “Halt” or “Not Halt”.But in case second program, when HM(X, X) will halt loop body tells to go in loop and when it doesn’t halt that means loop, it is asked to return.

Now we take one more situation where the program CM is passed to CM() function as an argument. Then there would be some impossibility, i.e., a condition arises which is not possible.

It is impossible for outer function to halt if its code (inner body) is in loop and also it is impossible for outer non halting function to halt even after its inner code is halting. So the both condition is non halting for CM machine/program even we had assumed in the beginning that it would halt.So this is the contradiction and we can say that our assumption was wrong and this problem, i.e., halting problem is undecidable.

Recursive and Recursively Enumerable language

Recursive Enumerable (RE) or Type -0 Language

RE languages or type-0 languages are generated by type-0 grammars. An RE language can be accepted or recognized by Turing machine which means it will enter into final state for the strings of language and may or may not enter into rejecting state for the strings which are not part of the language. It means TM can loop forever for the strings which are not a part of the language. RE languages are also called as Turing recognizable languages.

Recursive Language (REC)

A recursive language (subset of RE) can be decided by Turing machine which means it will enter into final state for the strings of language and rejecting state for the strings which are not part of the language. e.g.; L= {anbncn|n>=1} is recursive because we can construct a turing machine which will move to final state if the string is of the form anbncn else move to non-final state. So the TM will always halt in this case. REC languages are also called as Turing decidable languages. The relationship between RE and REC languages can be shown in Figure 1. 
 

 

Closure Properties of Recursive Languages

• Union: If L1 and If L2 are two recursive languages, their union L1∪L2 will also be recursive because if TM halts for L1 and halts for L2, it will also halt for L1∪L2.
• Concatenation: If L1 and If L2 are two recursive languages, their concatenation L1.L2 will also be recursive. For Example: 

    L1= {anbncn|n>=0} 
    L2= {dmemfm|m>=0}
    L3= L1.L2
    = {anbncndm emfm|m>=0 and n>=0} is also recursive.

• L1 says n no. of a’s followed by n no. of b’s followed by n no. of c’s. L2 says m no. of d’s followed by m no. of e’s followed by m no. of f’s. Their concatenation first matches no. of a’s, b’s and c’s and then matches no. of d’s, e’s and f’s. So it can be decided by TM.
• Kleene Closure: If L1is recursive, its kleene closure L1* will also be recursive. For Example:

         L1= {anbncn|n>=0}
         L1*= { anbncn||n>=0}* is also recursive.

• Intersection and complement: If L1 and If L2 are two recursive languages, their intersection L1 ∩ L2 will also be recursive. For Example: 

    L1= {anbncndm|n>=0 and m>=0} 
    L2= {anbncndn|n>=0 and m>=0}
    L3=L1 ∩ L2
    = { anbncndn |n>=0} will be recursive.

 

L1 says n no. of a’s followed by n no. of b’s followed by n no. of c’s and then any no. of d’s. L2 says any no. of a’s followed by n no. of b’s followed by n no. of c’s followed by n no. of d’s. Their intersection says n no. of a’s followed by n no. of b’s followed by n no. of c’s followed by n no. of d’s. So it can be decided by turing machine, hence recursive. 
Similarly, complement of recursive language L1 which is ∑*-L1, will also be recursive.

Note: As opposed to REC languages, RE languages are not closed under complementation which means complement of RE language need not be RE.

GATE Questions 

Question 1: Which of the following statements is/are FALSE? 
1.For every non-deterministic TM, there exists an equivalent deterministic TM. 
2.Turing recognizable languages are closed under union and complementation. 
3.Turing decidable languages are closed under intersection and complementation. 
4.Turing recognizable languages are closed under union and intersection.

A.1 and 4 
B.1 and 3 
C.2 
D.3

Solution:

Statement 1 is true as we can convert every non-deterministic TM to deterministic TM. 
Statement 2 is false as Turing recognizable languages (RE languages) are not closed under complementation. 
Statement 3 is true as Turing decidable languages (REC languages) are closed under intersection and complementation. 
Statement 4 is true as Turing recognizable languages (RE languages) are closed under union and intersection.

Question 2 : Let L be a language and L’ be its complement. Which one of the following is NOT a viable possibility? 
A.Neither L nor L’ is RE. 
B.One of L and L’ is RE but not recursive; the other is not RE. 
C.Both L and L’ are RE but not recursive. 
D.Both L and L’ are recursive.

Solution:

Option A is correct because if L is not RE, its complementation will not be RE. Option B is correct because if L is RE, L’ need not be RE or vice versa because RE languages are not closed under complementation. 
Option C is false because if L is RE, L’ will not be RE. But if L is recursive, L’ will also be recursive and both will be RE as well because REC languages are subset of RE. As they have mentioned not to be REC, so option is false. 
Option D is correct because if L is recursive L’ will also be recursive.

Question 3: Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

A.L1′ is recursive and L2′ is recursively enumerable 
B.L1′ is recursive and L2′ is not recursively enumerable 
C.L1′ and L2′ are recursively enumerable 
D.L1′ is recursively enumerable and L2′ is recursive 
Solution:

Option A is False as L2’ can’t be recursive enumerable (L2 is RE and RE are not closed under complementation). 
Option B is correct as L1’ is REC (REC languages are closed under complementation) and L2’ is not recursive enumerable (RE languages are not closed under complementation). 
Option C is False as L2’ can’t be recursive enumerable (L2 is RE and RE are not closed under complementation). 
Option D is False as L2’ can’t be recursive enumerable (L2 is RE and RE languages are not closed under complementation). As REC languages are subset of RE, L2’ can’t be REC as well.

Church’s Thesis

In 1936, A method named as lambda-calculus was created by Alonzo Church in which the Church numerals are well defined, i.e. the encoding of natural numbers. Also in 1936, Turing machines (earlier called theoretical model for machines) was created by Alan Turing, that is used for manipulating the symbols of string with the help of tape.

Church Turing Thesis :

Turing machine is defined as an abstract representation of a computing device such as hardware in computers. Alan Turing proposed Logical Computing Machines (LCMs), i.e. Turing’s expressions for Turing Machines. This was done to define algorithms properly. So, Church made a mechanical method named as ‘M’ for manipulation of strings by using logic and mathematics.

This method M must pass the following statements:

• Number of instructions in M must be finite.
• Output should be produced after performing finite number of steps.
• It should not be imaginary, i.e. can be made in real life.
• It should not require any complex understanding.

Using these statements Church proposed a hypothesis called Church’s Turing thesis that can be stated as: “The assumption that the intuitive notion of computable functions can be identified with partial recursive functions.”

In 1930, this statement was first formulated by Alonzo Church and is usually referred to as Church’s thesis, or the Church-Turing thesis. However, this hypothesis cannot be proved.

The recursive functions can be computable after taking following assumptions:

1. Each and every function must be computable.
2. Let ‘F’ be the computable function and after performing some elementary operations to ‘F’, it will transform a new function ‘G’ then this function ‘G’ automatically becomes the computable function.
3. If any functions that follow above two assumptions must be states as computable function.

Linear Bounded Automata

A linear bounded automaton is a multi-track non-deterministic Turing machine with a tape of some bounded finite length.

Length = function (Length of the initial input string, constant c)

Here,

Memory information ≤ c × Input information

The computation is restricted to the constant bounded area. The input alphabet contains two special symbols which serve as left end markers and right end markers which mean the transitions neither move to the left of the left end marker nor to the right of the right end marker of the tape.

A linear bounded automaton can be defined as an 8-tuple (Q, X, ∑, q0, ML, MR, δ, F) where −

• Q is a finite set of states

• X is the tape alphabet

• ∑ is the input alphabet

• q0 is the initial state

• ML is the left end marker

• MR is the right end marker where MR ≠ ML

• δ is a transition function which maps each pair (state, tape symbol) to (state, tape symbol, Constant ‘c’) where c can be 0 or +1 or -1

• F is the set of final states

A deterministic linear bounded automaton is always context-sensitive and the linear bounded automaton with empty language is undecidable..

Universal Turing machine

The Turing Machine (TM) is the machine level equivalent to a digital computer.

It was suggested by the mathematician Turing in the year 1930 and has become the most widely used model of computation in computability and complexity theory.

The model consists of an input and output. The input is given in binary format form on to the machine’s tape and the output consists of the contents of the tape when the machine halts

The problem with the Turing machine is that a different machine must be constructed for every new computation to be performed for every input output relation.

This is the reason the Universal Turing machine was introduced which along with input on the tape takes the description of a machine M.

The Universal Turing machine can go on then to simulate M on the rest of the content of the input tape.

A Universal Turing machine can thus simulate any other machine.

The idea of connecting multiple Turing machine gave an idea to Turing −

• Can a Universal machine be created that can ‘simulate’ other machines?

• This machine is called as Universal Turing Machine

This machine would have three bits of information for the machine it is simulating

• A basic description of the machine.
• The contents of machine tape.
• The internal state of the machine.

The Universal machine would simulate the machine by looking at the input on the tape and the state of the machine.

It would control the machine by changing its state based on the input. This leads to the idea of a “computer running another computer”.

It would control the machine by changing its state based on the input. This leads to the idea of a “computer running another computer”.

The schematic diagram of the Universal Turing Machine is as follows −

Examples of TM

Turing Machine for anbn where n>=1

Turing Machine for anbncnwhere n>=1

Example: Construct a Turing Machine for language L = {ww | w ∈ {0,1}}

The language L = {ww | w ∈ {0, 1}} tells that every string of 0’s and 1’s which is followed by itself falls under this language. The logic for solving this problem can be divided into 2 parts:

1. Finding the mid point of the string 
2. After we have found the mid point we match the symbols

Example – Lets understand it with the help of an example. Lets string 1 0 1 1 0 1, so w = 1 0 1 and string is of form (ww). 

The first thing that we do is to find the midpoint. For this, we convert 1 in the beginning into Y and move right till the end of the string. Here we convert 1 into y. 

Now our string would look like Y 0 1 1 0 Y. Now move left till, find a X or Y. When we do so, convert the 0 or 1 right of it to X or Y respectively and then do the same on the right end. Now our string would look like Y X 1 1 X Y. Thereafter, convert these 1’s also and finally it would look like Y X Y Y X Y. 

At this point, you have achieved the first objective which was to find the midpoint. Now convert all X and Y on the left of midpoint into 0 and 1 respectively, so string becomes 1 0 1 Y X Y. Now, convert the 1 into Y and move right till, find Y in the beginning of the right part of the string and convert this Y into a blank (denoted by B). Now string looks like Y 0 1 B X Y. 

Similarly, apply this on 0 and x followed by 1 and Y. After this string looks like Y X Y B B B. Now that you have no 0 and 1 and all X and Y on the right part of the string are converted into blanks so our string will be accepted. 

Assumption: We will replace 0 by X and 1 by Y. 

Approach Used – 

The first thing is to find the midpoint of the string, convert a 0 or 1 from the beginning of the string into X or Y respectively and a corresponding 0 or 1 into X or Y from the end of the string. After continuously doing it a point is reached when all 0’s and 1’s have been converted into X and Y respectively. At this point, you are on the midpoint of the string. So, our first objective is fulfilled. 

Now, convert all X’s and Y’s on the left of the midpoint into 0’s and 1’s. At this point the first half the string is in the form of 0 and 1. The second half of the string is in the form of X and Y. 

Now, start from the beginning of the string. If you have a 0 then convert it into X and move right till reaching the second half, here if we find X then convert it into a blank(B). Then traverse back till find an X or a Y. We convert the 0 or 1 on the right of it into X or Y respectively and correspondingly, convert its X or Y in the second half of string into a blank(B). 

Keep doing this till converted all symbols on the left part of the string into X and Y and all symbols on the right of string into blanks. If any one part is completely converted but still some symbols in the other half are left unchanged then the string will not be accepted. If you did not find an X or Y in the second half for a corresponding 0 or 1 respectively in the first half. Then also string will not be accepted. 

Examples: 

 

Input  : 1 1 0 0 1 1 0 0 
Output : Accepted

Input  : 1 0 1 1 1 0 1
Output : Not accepted

 

• Step-1: 
  If the symbol is 0 replace it by X and move right 
  If the symbol is 1 replace it by Y and move right, 
  Go to state Q1 and step 2 
  ——————————————— 
  If the symbol is X replace it by X and move left or 
  If the symbol is Y replace it by Y and move left, 
  Go to state Q4 and step 5 

   

• Step-2: 
  If the symbol is 0 replace it by 0 and move right, remain on the same state 
  If the symbol is 1 replace it by 1 and move right, remain on the same state 
  ——————————————— 
  If the symbol is X replace it by X and move left or 
  If the symbol is Y replace it by Y and move left or 
  If the symbol is $ replace it by $ and move left, Go to state Q2 and step 3 

   

• Step-3: 
  If symbol is 0 replace it by X and move left, or 
  If symbol is 1 replace it by Y and move left, 
  Go to state Q3 and step 4 

   

• Step-4: 
  If the symbol is 0 replace it by 0 and move left, remain on the same state 
  If the symbol is 1 replace it by 1 and move left, remain on the same state 
  ——————————————— 
  If the symbol is X replace it by X and move right or 
  If the symbol is Y replace it by Y and move right, 
  Go to state Q0 and step 1 

   

• Step-5: 
  If symbol is X replace it by X and move left or 
  If symbol is Y replace it by Y and move left 
  Go to state Q4 and step 6 

   

• Step-6: 
  If symbol is X replace it by 0 and move left, remain on same state 
  If symbol is Y replace it by 1 and move left, remain on same state 
  – – – – – – – – – — – – – – – – – – – — 
  If symbol is $ replace it by $ and move right 
  Go to state Q4 and step 7 

   

• Step-7: 
  If symbol is 0 replace it by X and move right, go to state Q6 and step 8 
  If symbol is 1 replace it by Y and move right, go to state Q7 and step 9 
  – – – – – – – – – — – – – – – – – – – — 
  If symbol is B replace it by B and move left, STRING ACCEPTED, GO TO FINAL STATE Q9 

   

• Step-8: 
  If symbol is 0 replace it by 0 and move right, remain on same state 
  If symbol is 1 replace it by 1 and move right, remain on same state 
  If symbol is B replace it by B and move right, remain on same state 
  – — – – – – – – – – – – – – – – – – – – 
  If symbol is X replace it by B and move left 
  Go to state Q8 and step 10 

   

• Step-9: 
   

If symbol is 0 replace it by 0 and move right, remain on same state 

If symbol is 1 replace it by 1 and move right, remain on same state 

If symbol is B replace it by B and move right, remain on same state 

– — – – – – – – – – – – – – – – – – – – 

If symbol is Y replace it by B and move left 

Go to state Q8 and step 10 

 

• Step-10: 
  If symbol is 0 replace it by 0 and move left, remain on same state 
  If symbol is 1 replace it by 1 and move left, remain on same state 
  If symbol is B replace it by B and move left, remain on same state 
  – — – – – – – – – – – – – – – – – – – – 
  If symbol is Y replace it by Y and move right or 
  If symbol is X replace it by X and move right 
  Go to state Q5 and step 7 
   

 

Example:

Construct a TM for the language L = {0ⁿ1ⁿ2ⁿ} where n≥1

Solution:

L = {0ⁿ1ⁿ2ⁿ | n≥1} represents language where we use only 3 character, i.e., 0, 1 and 2. In this, some number of 0's followed by an equal number of 1's and then followed by an equal number of 2's. Any type of string which falls in this category will be accepted by this language.

The simulation for 001122 can be shown as below:

Now, we will see how this Turing machine will work for 001122. Initially, state is q0 and head points to 0 as:

The move will be δ(q0, 0) = δ(q1, A, R) which means it will go to state q1, replaced 0 by A and head will move to the right as:

The move will be δ(q1, 0) = δ(q1, 0, R) which means it will not change any symbol, remain in the same state and move to the right as:

The move will be δ(q1, 1) = δ(q2, B, R) which means it will go to state q2, replaced 1 by B and head will move to right as:

The move will be δ(q2, 1) = δ(q2, 1, R) which means it will not change any symbol, remain in the same state and move to right as:

The move will be δ(q2, 2) = δ(q3, C, R) which means it will go to state q3, replaced 2 by C and head will move to right as:

Now move δ(q3, 2) = δ(q3, 2, L) and δ(q3, C) = δ(q3, C, L) and δ(q3, 1) = δ(q3, 1, L) and δ(q3, B) = δ(q3, B, L) and δ(q3, 0) = δ(q3, 0, L), and then move δ(q3, A) = δ(q0, A, R), it means will go to state q0, replaced A by A and head will move to right as:

The move will be δ(q0, 0) = δ(q1, A, R) which means it will go to state q1, replaced 0 by A, and head will move to right as:

The move will be δ(q1, B) = δ(q1, B, R) which means it will not change any symbol, remain in the same state and move to right as:

The move will be δ(q1, 1) = δ(q2, B, R) which means it will go to state q2, replaced 1 by B and head will move to right as:

The move will be δ(q2, C) = δ(q2, C, R) which means it will not change any symbol, remain in the same state and move to right as:

The move will be δ(q2, 2) = δ(q3, C, L) which means it will go to state q3, replaced 2 by C and head will move to left until we reached A as:

immediately before B is A that means all the 0's are market by A. So we will move right to ensure that no 1 or 2 is present. The move will be δ(q2, B) = (q4, B, R) which means it will go to state q4, will not change any symbol, and move to right as:

The move will be (q4, B) = δ(q4, B, R) and (q4, C) = δ(q4, C, R) which means it will not change any symbol, remain in the same state and move to right as:

The move δ(q4, X) = (q5, X, R) which means it will go to state q5 which is the HALT state and HALT state is always an accept state for any TM.

The same TM can be represented by Transition Diagram:

Example 2:

Construct a TM machine for checking the palindrome of the string of even length.

Solution:

Firstly we read the first symbol from the left and then we compare it with the first symbol from right to check whether it is the same.

Again we compare the second symbol from left with the second symbol from right. We repeat this process for all the symbols. If we found any symbol not matching, we cannot lead the machine to HALT state.

Suppose the string is ababbabaΔ. The simulation for ababbabaΔ can be shown as follows:

Now, we will see how this Turing machine will work for ababbabaΔ. Initially, state is q0 and head points to a as:

We will mark it by * and move to right end in search of a as:

We will move right up to Δ as:

We will move left and check if it is a:

It is 'a' so replace it by Δ and move left as:

Now move to left up to * as:

Move right and read it

Now convert b by * and move right as:

Move right up to Δ in search of b as:

Move left, if the symbol is b then convert it into Δ as:

Now move left until * as:

Replace a by * and move right up to Δ as:

We will move left and check if it is a, then replace it by Δ as:

It is 'a' so replace it by Δ as:

Now move left until *

Now move right as:

Replace b by * and move right up to Δ as:

Move left, if the left symbol is b, replace it by Δ as:

Move left till *

Move right and check whether it is Δ

Go to HALT state

The same TM can be represented by Transition Diagram:

Example 3:

Construct a TM machine for checking the palindrome of the string of odd length.

Solution:

Firstly we read the first symbol from left and then we compare it with the first symbol from right to check whether it is the same.

Again we compare the second symbol from left with the second symbol from right. We repeat this process for all the symbols. If we found any symbol not matching, we lead the machine to HALT state.

Suppose the string is 00100Δ. The simulation for 00100Δ can be shown as follows:

Now, we will see how this Turing machine will work for 00100Δ. Initially, state is q0 and head points to 0 as:

Now replace 0 by * and move right as:

Move right up to Δ as:

Move left and replace 0 by Δ and move left:

Now move left up to * as:

Move right, convert 0 by * and then move right as:

Moved right up to Δ

Move left and replace 0 by Δ as:

Move left till * as:

Move right and convert 1 to * as:

Move left

Since it is *, goto HALT state.

The same TM can be represented by Transition Diagram:

Example 4:

Construct TM for the addition function for the unary number system.

Solution:

The unary number is made up of only one character, i.e. The number 5 can be written in unary number system as 11111. In this TM, we are going to perform the addition of two unary numbers.

For example

2 + 3
i.e. 11 + 111 = 11111

If you observe this process of addition, you will find the resemblance with string concatenation function.

In this case, we simply replace + by 1 and move ahead right for searching end of the string we will convert last 1 to Δ.

Input: 3+2

The simulation for 111+11Δ can be shown as below:

Move right up to + sign as:

Convert + to 1 and move right as:

Now, move right

Again move right

Now Δ has encountered, so just move left as:

Convert 1 to Δ

Thus the tape now consists of the addition of two unary numbers.

The TM will look like as follows:

Here, we are implementing the function of f(a + b) = c. We assume a and b both are non zero elements.

Example 5:

Construct a TM for subtraction of two unary numbers f(a-b) = c where a is always greater than b.

Solution: Here we have certain assumptions as the first number is greater than the second one. Let us assume that a = 3, b = 2, so the input tape will be:

We will move right to - symbol as perform reduction of a number of 1's from the first number. Let us look at the simulation for understanding the logic:

Move right up to - as:

Move right and convert 1 to * as:

Now move left

Again move left

Convert 1 to * and move right-hand

Now move right till 1

Convert 1 to * and move left

Convert 1 to * and move

Move right till Δ as:

Now we are in the HALT state.

Thus we get 1 on the input tape as the answer for f(3-2).

The Turing machine will look like this: