Unit – 5

Turing Machine

5.1 Basic model, definition and representation

An information processing system is associate acceptive device that accepts the languages (recursively calculable set) generated by sort zero grammars. It had been fancied in 1936 by Alan Turing.

Representation of Turing Machines

An information processing system (TM) may be a mathematical model that consists of

Associate infinite length tape divided into cells on which input is given. It consists of a head that reads the input tape.

A state register stores the state of the information processing system. Once reading an

Associated input image, it’s replaced with another image, its internal state is modified, and it moves from one cell to the proper or left. If the metal reaches the ultimate state, the input string is accepted, otherwise rejected.

A metal will be formally delineated as a 7-tuple (Q, X, ∑, δ, q0, B, F)

Where −

• Q may be a finite set of states

• X is that the tape alphabet

• ∑ is that the input alphabet

• δ may be a transition function; δ: alphabetic character × X → alphabetic character       × X ×

• q0 is that the initial state

• B is that the blank image

• F is that the set of ultimate states

Time and area quality of an information processing system

For an information processing system, the time quality refers to the live of variety|the amount|the quantity} of times the tape moves once the machine is initialized for a few input symbols and therefore the area quality is that the number of cells of the tape written.

Time quality all affordable functions −

T(n) = O (n log n)

TM’s area quality

S(n) = O(n)

5.2 Instantaneous Description

All symbols are to the left of the head, the machine is in the state of scanning, and all symbols are to the right of the head, i.e.

(X1 X2 …… Xi-1q Xi …… Xn)

As previously demonstrated, a Turing machine accepting a string with equal amounts of zeros and ones cannot be done using FA.

Turing machine programming can be done purely in finite state logic, but it can also be done with data on tape.

By including tape symbol dependent states in finite state logic, it can also be utilized to store data.

A Turing machine's instantaneous description or configuration involves (1) the Turing machine's current state, (2) the contents of the tape, and (3) the position of the tape head on the tape. This can be summed up in a string that looks like this:

xi...xjqmxk...xl

The symbols on the tape are represented by the xs, the current state is represented by qm, and the tape head is located on the square containing xk (the symbol immediately following qm).

Key takeaway

A Turing machine's instantaneous description or configuration involves (1) the Turing machine's current state, (2) the contents of the tape, and (3) the position of the tape head on the tape.

5.3 Language Acceptability by Turing Machines

Even though they are recursively enumerable, the Turing machine embraces all the language. Recursive implies repeating for any number of times the same set of rules, and enumerable means a collection of elements.

Computable attributes, such as addition, multiplication, subtraction, division, power function, and many more are also accepted by the TM.

Example: Creating a turning machine which accepts the language of aba over ∑ = {a, b}

Sol: We'll think that the string 'aba' is positioned like this on the input tape:

The tape head reads the sequence up to the Δ characters. If the tape head is read 'aba' string, then after reading, TM will stop.

Now we're going to see how this turbo machine is going to work for aba. The condition is originally q0 and the head points to an as:

The next move are δ(q0, a) = δ(q1, A, R) which means it goes to state q1, replaced by A and  head moves toward  right :

The next move are δ(q1, b) = δ(q2, B, R) which means it goes to state q2 , replaced by B and  head moves toward  right :

The next move are δ(q2, a) = δ(q3, A, R) which means it goes to state q3 , replaced by A and  head moves toward  right :

The move δ(q3, Δ) = (q4, Δ, S) therefore, it will go to state q4 which is the HALT state and HALT state is always an accept state for any Turing Machine .

The Turing machine can be represented by transition diagram -

Fig: Transition diagram for Turing machine

Key takeaway

Even though they are recursively enumerable, the Turing machine embraces all the language. Recursive implies repeating for any number of times the same set of rules, and enumerable means a collection of elements.

Computable attributes, such as addition, multiplication, subtraction, division, power function, and many more are also accepted by the TM.

5.4 Variants of Turing Machine

1. Multiple tracks Alan Turing Machine:

• A k-tack Alan Turing machine(for some k>0) has k-tracks and one R/W head that reads and writes all of them one by one.

•   A k-track information processing system may be simulated by one track information processing system

2. Two-way infinite Tape Alan Turing Machine:

• Infinite tape of two-way infinite tape information processing system is boundless in each directions left and right.

• Two-way infinite tape information processing system may be simulated by unidirectional infinite {turing|Turing|Alan Alan Turing|Alan Mathison Turing|mathematician} machine(standard Turing machine).

3. Multi-tape Alan Turing Machine:

• It has multiple tapes and controlled by one head.

• The Multi-tape information processing system is completely different from k-track information processing system however communicative power is same.

•   Multi-tape information processing system may be simulated by single-tape information processing system.

4. Multi-tape Multi-head Alan Turing Machine:

• The multi-tape information processing system has multiple tapes and multiple heads

• Each tape controlled by separate head

•   Multi-Tape Multi-head information processing system may be simulated by normal information processing system.

5. Multi-dimensional Tape Alan Turing Machine:

• It has multi-dimensional tape wherever head will move any direction that's left, right, up or down.

•   Multi-dimensional tape information processing system may be simulated by one-dimensional information processing system.

6. Multi-head Alan Turing Machine:

• A multi-head information processing system contain 2 or additional heads to scan the symbols on constant tape.

• In one step all the heads sense the scanned symbols and move or write severally.

•   Multi-head information processing system may be simulated by single head information processing system.

7. Non-deterministic Alan Turing Machine:

• A non-deterministic information processing system encompasses a single, a method infinite tape.

• For a given state and input image has atleast one option to move (finite range of decisions for consecutive move), every selection many decisions of path that it'd follow for a given input string.

• A non-deterministic information processing system is adored settled information processing system.

5.5 Turing Machine as Computer of Integer Functions

Simulating a TM by Computer -

➢      A real computer is actually a finite automaton!

➢      Simulation of an infinite memory space by “storage swapping.”

➢      Also, simulation of an infinite tape of the TM by two stacks of disks, respectively for the left portion and the right portion of the tape, with the head as the middle.

Simulating a Computer by a TM -

Sketch of using a Multitape TM to simulate the sequence of instructions of the computer and use a TM tape:

• As the computer memory;

• To simulate the instruction counter;

• For the memory address;

• As scratch to perform computation operations on it.

5.6 Universal Turing machine

The mathematical device similar to a digital computer is the Turing Machine. It was proposed in the 1930s by the mathematician Turing, and has been the most commonly used computer model in the theory of computability and complexity since then.

The model consists of an input relationship between the output that the computer calculates. On the machine's tape, the input is supplied in binary form, and the output consists of the tape content when the machine stops.

Within the Turing Machine, what decides how the contents of the tape shift is a finite state machine (or FSM, also called a finite automaton). The FSM has been the number of states it has and the transitions between them are determined by the number.

The current state and the character read on the tape decide at each step the next state that the FSM will be in the character that the computer will generate on the tape (possibly the one that reads, leaving the contents unchanged), and the direction in which the head travels, left or right.

The problem with Turing Machines is that for each new computation to be performed, for each input output reference, a separate one must be constructed.

This is why we are implementing the idea of a Universal Turing Machine (UTM), which   the definition of a system M is used along with the input on the tape. The UTM will then simulate M on the rest of the content of the input tape to simulate.

A universal Turing machine can thus simulate any other machine.

Fig: Universal Turing machine

Key takeaways:

-         A mathematical model consisting of an associated infinite length tape divided into cells on which input is given may be an information processing device (TM)

-         Computable attributes, such as addition, multiplication, subtraction, division, power function, and many more are also accepted by the TM.

-         A real computer is actually a finite automaton.

5.7 Church’s Thesis

In 1936, a technique named as lambda-calculus was created by Alonzo Church within which the Church numerals area unit well outlined, i.e., the encryption of natural numbers. Additionally in 1936, mathematician machines (earlier known as theoretical model for machines) was created by mathematician, that’s used for manipulating the symbols of string with the assistance of tape.

Church mathematician Thesis:

Turing machine is outlined as associate degree abstract illustration of a computer like hardware in computers. Mathematician planned Logical Computing Machines (LCMs), i.e., mathematician’s expressions for Turing Machines. This was done to outline algorithms properly. So, Church created a mechanical methodology named as ‘M’ for manipulation of strings by mistreatment logic and arithmetic.

This methodology M should pass the subsequent statements:

• Number of directions in M should be finite.

• Output ought to be made when playing a finite variety of steps.

• It mustn’t be imagined, i.e., is created in the world.

• It mustn’t need any complicated understanding.

Using these statements Church planned a hypothesis known as Church’s mathematician thesis that may be expressed as: “The assumption that the intuitive the notion of estimable functions is known with partial algorithmic functions.”

In 1930, this statement was initial developed by Alonzo Church and is typically brought up as Church’s thesis, or the Church-Turing thesis. However, this hypothesis cannot be proved.

The algorithmic functions are estimable when taking following assumptions:

1. Every and each operate should be estimable.
2. Let ‘F’ be the estimable operate and when playing some elementary operations to ‘F’, it’ll rework a replacement operate ‘G’ then this operates ‘G’ mechanically becomes the estimable operate.
3. If any operates that follow on top of 2 assumptions should be states as an estimable function.

Key takeaway

For manipulation of strings by mistreatment logic and arithmetic, Church developed a mechanical technique called ‘M'.

In 1936, a technique named as lambda-calculus was created by Alonzo Church within which the Church numerals area unit well outlined, i.e., the encryption of natural numbers.

5.8 Recursive and Recursively Enumerable language

Recursive language (RE) –

A language ‘L’ is alleged to be algorithmic if there exists a computing device which is able to settle for all the strings in ‘L’ and reject all the strings not in ‘L’. The computing device can halt on every occasion and provides associate answer (accepted or rejected) for every and each string input. A language ‘L’ is decidable if it’s an algorithmic language. All decidable languages area unit algorithmic languages and vice-versa.

Recursively countable language (RCE) –

A language ‘L’ is alleged to be a recursively countable language if there exists a computing device which is able to settle for (and so halt) for all the input strings that area unit in ‘L’ however could or might not halt for all input strings that aren’t in ‘L’.

By definition, all REC languages {are also| area unit|are} RE languages however not all RE languages are REC languages.

A language is termed Decidable or algorithmic if there’s a data processor that accepts and halts on each input string w. Each decidable language is Turing-Acceptable.

Fig: Each decidable language is Turing-Acceptable.

A decision downside P is decidable if the language L of all affirmative instances to P is decidable.

For a decidable language, for every input string, the thulium halts either at the settle for or the reject state as pictured within the following diagram –

Fig: Turing machine

Key takeaway

A language ‘L’ is alleged to be algorithmic if there exists a computing device which is able to settle for all the strings in ‘L’ and reject all the strings not in ‘L’.

A language ‘L’ is alleged to be a recursively countable language if there exists a computing device which is able to settle for (and so halt) for all the input strings that area unit in ‘L’ however could or might not halt for all input strings that aren’t in ‘L’.

5.9 Halting Problem

Input: A Turing machine and an input string T.

Problem - Does the Turing machine complete the T-string computation in a finite number of steps? Either yes or no must be the answer.

Sol:  We will first assume that there is such a Turing machine to solve this problem, and then we will demonstrate that it contradicts itself. This Turing machine would be called a Halting machine that produces in a finite amount of time a 'yes' or no'. The performance comes as 'yes' if the stopping machine finishes in a finite amount of time, otherwise as no'.

The following is a Halting Computer block diagram -

Fig: Halting machine

Now we will design an inverted halting machine (HM)’ as -

●      If H returns YES, then loop forever.

●      If H returns NO, then halt.

Below is the block diagram of inverted halting machine -

Fig: Inverted halting machine

In addition, as follows, a machine (HM)2 whose input itself is constructed -

●      If - (HM)2 halts on input, loop forever

●      Else - halt

Now, we have a contradiction. So, the halting problem is undecidable.

5.10 Introduction to Undecidability

If there is no Turing machine that will always cease in a finite amount of time to deliver a yes or no answer, the problem is undecidable. There is no technique for determining the answer to an undecidable problem for a given input.

We frequently come across similar situations in the theory of computation where the answer is either 'yes' or 'no.' Solvable or decidable problems are those that can be answered with a yes or no. Otherwise, the problem category is referred to as unsolvable or undecidable.

Example

Ambiguity of context-free languages:  There is no Turing machine that, given a context-free language, will always halt in a finite amount of time and say whether the language is ambiguous or not.

Equivalence of two context-free languages:  There is no Turing computer that, given two context-free languages, will always halt in a finite amount of time and say whether the languages are equal or not.

Everything or completeness of CFG: It is unclear whether CFG will generate all possible strings of input alphabet (*) given a CFG and input alphabet.

Regularity of CFL, CSL, REC and REC: It's impossible to say whether a CFL, CSL, REC, or REC is regular given a CFL, CSL, REC, or REC.

Undecidability of Universal Languages:

The universal communication system We must show that Lu is undecidable because it is a recursively enumerable language (non-recursive).

Theorem - Lu is a recursive but not a recursive RE.

Proof - Consider the fact that the language Lu is recursively enumerable. Lu will be assumed to be recursive. The complement of Lu, which is Lu, is recursive as well. We can, however, construct a TM Ld if we have a TM M that accepts Lu. The diagonalization language Ld, on the other hand, is not RE. As a result, our assumption that Lu is recursive is incorrect (not RE means not recursive). As a result, we can argue Lu is RE but not recursive. The following graphic depicts the creation of M for Ld

Fig: Construction of M’ for Ld

Key takeaway

If there is no Turing machine that will always cease in a finite amount of time to deliver a yes or no answer, the problem is undecidable. There is no technique for determining the answer to an undecidable problem for a given input.

5.11 Undecidable problems about TMs

In this segment, we'll go over all of the Turing machine's unsolved issues. The reduction is used to demonstrate whether or not a given language is desirable. We will first learn about the concept of reduction in this section, and then we will look at a key theorem in this area.

Reduction

If a problem P1 is reduced to a problem P2, then any solution to P2 solves P1. In general, a P1 reduced P2 algorithm is one that converts an instance of a problem P1 to an instance of a problem P2 that has the same answer. As a result, if P1 is not recursive, neither is P2. Similarly, if P1 is not recursively enumerable, then neither is P2.

Theorem: When P1 is decreased to P2, the result is -

1. If P1 is inconclusive, then P2 is equally inconclusive.

2. If P1 isn't RE, then P2 isn't either.

Proof:

1. Consider the case w of P1. Then create an algorithm that accepts instance w as an input and changes it to instance x of P2. After that, use that algorithm to see if x is in P2. If the algorithm returns 'yes,' then x is in P2. We may also state that w is in P1 if the algorithm returns 'yes.' P2 has been obtained after P1 has been reduced. Similarly, if the algorithm returns 'no,' then x is not in P2 and w is not in P1. This demonstrates that if P1 is undecidable, then P1 is undecidable as well.
2. P1 is assumed to be non-RE, while P2 is assumed to be RE. Create an algorithm to decrease P1 to P2, however only P2 will be recognized by this algorithm. That means a Turing machine will say 'yes' if the input is in P2, but may or may not halt if the input is not in P2. We know that an instance of w in P1 can be converted to an instance of x in P2. After then, use a TM to see if x is in P2. If x is approved, then w must likewise be accepted. This procedure explains a TM that speaks the P1 language. If w is in P1, then x is in P2, and vice versa. If w is not in P1, then x is not in P2. This establishes that if P1 is non-RE, then P2 must be non-RE as well.

5.12 Post’s Correspondence Problem

It was introduced by Emil Post and is an undecidable decision problem. The PCP problem over an alphabet ∑ is stated as follows −

Given the following two lists, M and N of non-empty strings over ∑ −

M = (x 1, x 2, x 3 ,………, x n )

N = (y 1, y 2, y 3 ,………, y n )

We can say that there is a Post Correspondence Solution, if for some i 1, i 2……… i k,

Where 1 ≤ i j ≤ n, the condition x i1 …….x ik = y i1 ……. y ik satisfies.

Example 1

Find whether the lists

M = (abb, aa, aaa) and N = (bba, aaa, aa)

Have a Post Correspondence Solution?

Sol:

Here,

x2 x1 x3= ‘aaabbaaa’

And y2 y1 y3= ‘aaabbaaa’

We can see that

x2 x1 x3= y2 y1 y3

Hence, the solution is i = 2, j = 1, and k = 3.

Example 2

Find whether the lists M = (ab, bab, bbaaa) and N = (a, ba, bab) have a Post

Correspondence Solution?

Sol:

In this case, there is no solution because −

| x 2 x 1 x 3 | ≠ | y 2 y 1 y 3 | (Lengths are not same)

Hence, it can be said that this Post Correspondence Problem is undecidable.

5.13 Modified PCP

The first pair on the A and B lists must be the first pair in the solution, which is an additional condition in MPCP. For some integer k, an instance of MPCP is two lists A=w1,w2, w3,......wk and B=x1,x2,x3,......xk. A solution is a list of 0 or more numbers i1, i2,...., im such that w1wi1wi2...... Wim =x1 xi1 xi2...... Xim.

The modified PCP problem can be reduced to the PCP problem in the following way:

•   An MPCP instance with lists A = (w1, w2,..., wk) and B = (x1, x2,..., xk) is provided.

•   Assume that the symbols * and $ are new.

•   We create a PCP instance (C, D) from (A, B) with

C = (y0, y1, …, yk+1) and D = (z0, z1, …, zk+1) where

•   yi is wi with a * after each symbol in wi, for i = 1, 2, ..., k.

•   zi is xi with a * before each symbol in xi, for i = 1, 2, ..., k.

•   y0 = *y1 and yk+1 = $.

•   z0 = z1 and zk+1 = *$.

•   If 0, i1, i2,..., im, ik+1 is a solution to this constructed (C, D)-PCP instance, then i1, i2,..., im is a solution to the supplied (A,B)-MPCP instance.

Why MPCP

•   We employ MPCP to demonstrate that PCP is undecidable.

• We begin by reducing Lu (ATM) to an MPCP instance.

• The MPCP instance is reduced to a PCP instance.

•   It becomes easier to prove that PCP is undecidable as a result of decreases from Lu to PCP as MPCP in the middle.

5.14 Introduction to Recursive Function Theory

Total recursive function -

If f(a1, a2, ...an) is defined for all its arguments, a recursive function is called the complete recursive function. Let f(a1, a2, ...an) be a function defined for function g(b1, b2, ...bn). If each element of f is assigned to a unique element of function g, then f is a total function.

●      A complete function is called recursive or primitive recursive if and only if it is an initial over-n function, or if it is obtained by applying a finite number of times composition or recursion to an initial over-n function.

●      A complete recursive function or primitive recursive function is the multiplication of two positive integers.

●      Not all complete recursive functions are recursive primitive functions.

●      The function of Ackerman is a complete function.

●      Both primitive recursive features are complete functions.

Partial recursive function -

A function f(a1, a2,....an) determined by a TM is referred to as a partial recursive function. If f is defined for some but not all values of a1, a2,....an. Let f(a1, a2,...an) be a function defined by function g(b1, b2,....bn), then f is a partial function if almost one element of function g is assigned to some element of f.

If it is an initial function over N, a partial function is recursive, or if it is obtained by applying recursion or composition or minimization to an initial function over N.

●      The partial recursive function is the subtraction of two positive integers.

●      The partial function composition yields a partial(total) function.

●      A partial recursive function is the minimization of a complete recursive function.

References:

1.Introduction to Automata Theory, Languages, and Computation, 2e by John E, Hopcroft, Rajeev Motwani, Jeffery D. Ullman, Pearson Education.

2.Theory of Computer Science (Automata, Languages and Computation), 2e by K. L. P. Mishra and N. Chandrasekharan, PHI

3.Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, Pearson Education Asia.