Introduction to Turing Machine

Introduction to Turing Machine

FA

PDA

TM
TMs are able to do any of the following Operations on Tape
1) Read a symbol from the tape.
2) Write a symbol to the tape.
3) Move the tape head, one step LEFT.
4) Move the tape head, one step RIGHT.
 Components of Turing Machine
TAPE:
A 2-way infinite tape, divided into cells.Each cell is capable of holding only one tape symbol.
Purpose: Acts as the machine’s memory, allowing it to read from and write to the tape.

TAPE HEAD:

A read/write head that moves along the tape. It can read the symbol in the current cell, write a new
symbol, and move left or right.

Purpose: Facilitates interaction with the tape by reading symbols and updating them.

FINITE CONTROL UNIT:

The finite control unit is the part of the Turing Machine that contains the transition function and
manages the state transitions.
Purpose: It acts as the decision-making component that directs the machine's actions based on its
current state and the input symbol it encounters
Formal Definition
M = (Q, Σ, Γ, δ, q0, B, F)

● Q: The finite set of states

● Σ: The finite set of input symbols.
● Γ: The complete set of tape symbols, Σ is always a subset of Γ.
● δ: The transition function. Defines the next state assumed by the machine, the symbol

to be written in the tape, and the direction which the head will moves. δ:Q×Γ→Q×Γ×

{L,R}
● q0: The start state, a member of Q, where the finite control is found initially.
● B: the blank symbol. This symbol is in Γ but not in Σ.
● F: the set of final or accepting states, a subset of Q.
Church’s Thesis
 Church’s Thesis
According to the Church-Turing thesis:

-Anything that can be done on any existing digital computer can also be done by a Turing
machine/ Everything that can be computed, can be computed by a Turing machine / What
could naturally be called as an effective procedure, can be realized by a turing machine.

- This thesis cannot be proven but is believed on the basis of the amount of evidence that
supports it. No one has yet been able to suggest a problem, solvable by what we intuitively
consider an algorithm, for which a Turing machine program cannot be written.

- Computer scientists have devised several alternative models of computation, but none of
them is more powerful than the Turing machine model.

"Any real-world computation can be translated into an equivalent Turing machine

computation."
Design a Turing machine for a^n b^n | n ≥ 1
Design a Turing machine for a^n b^n c^n| n ≥ 1
Turing machine for converting unary number into binary number
Turing machine for addition of two number in unary
Turing machine for L = {w c w | w ∊ {0, 1}* }?
 Universal Turing Machine (UTM)
Motivation: We need a single m/c which can solve all type of problems
❖ A Universal Turing Machine is a reprogrammable Turing machine capable of simulating
the behavior of any other Turing machine, effectively serving as a programmable computer
that can execute any computable function.

❖ A standard Turing machine can simulate only a single computation problem, so if we want
to solve another computation problem, then another Turing machine is required to be
constructed, but in case of a UTM, the same UTM can be used to solve any computation
problem.

❖ Power of a UTM is the same as the power of a standard TM as both solve the same set of
computational problems. (also a digital computer)

❖ Turing complete means a system can perform any computation that a Turing machine can,
given enough time and memory.
 Universal Turing Machine (UTM)
Input to UTM is description of TM () and string w.
It consists of 3 tapes:
1. 1st tape stores the binary encoding of TM.
2. 2nd tape stores string w.
3. 3rd tape stores the state of TM.
Action: Accept, Reject, Loop
 Linear Bounded Automaton (LBA)

An LBA is a restricted type of Turing Machine where the tape is bounded by the length of the input.
LBAs are precisely the machines that recognize context-sensitive languages.
LBA is more powerful than PDA but less powerful than unrestricted Turing Machines.

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
 Recursive & Recursive Enumerable Language
Recursive Language (REC) {Turing Dec.}
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. The TM will always halt in this case. REC languages are also
called as Turing decidable languages. Recursive languages are not closed under following
operations • Kleen closure • Homomorphism • Substitution
Recursive Enumerable (RE) or Type -0 Language {Turing Rec.}
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. RE are
not closed under following operations • Compliment • Set Difference
 Halting Problem
Halt : The state of Turing machine, where no transition is defined or required is
known as Halt.
After taking an input string, there are three possibilities for Turing Machine, i.e. it
may go to:
● Final halt
● Non- Final halt
● Infinite loop
In case of Final Halt, Machine halts on final state, and hence it shows that string
is accepted. In Non-Final Halt, Machine halts on non- final state, and hence the
string is rejected.If the machine goes to infinite loop after taking an input string,
then we can’t say whether the string is Accepted/Rejected.
 Halting Problem
The Halting Problem in Automata theory is a problem that asks whether a
given computer program (Turing machine) will eventually stop running (halt)
or continue to run forever when provided with a specific input.
Problem: Determine if a program halts on a given input.
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.
 Post Correspondence Problem (PCP)

It is a popular undecidable problem that was introduced by Emil Leon Post in

1946.

The problem involves two lists of words over a common alphabet.

The challenge is to find a sequence of indices where the concatenation of the
words in the first list, in that sequence, is equal to the concatenation of the words
in the second list in the same sequence

Def 2: we have N number of Dominos (tiles). The aim is to arrange tiles in such
order that string made by Numerators is same as string made by Denominators.
 PCP Examples

A = {1, 110, 0111} • B =

{111, 001, 11}
PCP Examples
 Modifications of Turing Machine
1. Multi-tape Turing Machine
2. Turing Machine with stay option d: Q ×ℾ -> Q× ℾ × (L/R/S)
3. Multi-dimensional Turing Machine d: Q ×ℾ -> Q× ℾ × (L/R/U/D)
4. Turing Machine with one way infinite tape (Semi infinite tape)
5. Multi Read/Write head points
6. Multi-head Turing Machine
7. Offline TM: have a restriction that input can’t be changed (2 tapes)
8. Jumping TM: where the tape head can jump to non-adjacent positions on the tape
9. Non erasing TM: where input can not be converted to blank
10. Always writing TM
11. UTM
12. Non-Deterministic Turing Machine
13. TM without Writing Capacity (FA)
14. TM with Tape used as Stack
15. TM with finite tape
16. TM with Input Size Tape (LBA)
 Turing Machine as Computer of Integer Functions

● An integer function is a function that accepts integers as input and produces an

integer as output.

● Let an integer function be f (x,y) = x+y. We have to solve this function using Turing
Machine. so , input tape must represent the input arguments.

● Let the number of '0' be used to represent the argument. But there must be a separator
to differentiate the number of '0' for each argument. In Turing machine, blank space is
used to separate the arguments on the tape.
 Recursive Function Theory
Not all functions, even those with precise definitions, can be computed by Turing Machines.
Example: Busy Beaver Functions
If you can define a given function using initial primitive recursive functions, then it is a Turing computable function/primitive
recursive function.
So, some initial functions are taken as primitive recursive functions.
Recursive Function Theory
 Recursive Function Theory
Recursive Function
A recursive function is a function that calls itself during its execution. Eg:factorial

Partial Recursive Function

A function is called a partial recursive function if it is defined for some of its arguments. They may not
produce a result for every possible input. In other words, they can be undefined for some inputs.

Example: Subtraction of two positive numbers m and n, f(m, n) = m-n; if m>=n, otherwise its not
defined.

Primitive Recursive Functions: These are a subset of recursive functions that are defined using
only basic initial functions (such as zero, successor, and projection functions) and can be formed
through a finite combination of composition and recursion. They are always total functions, meaning
they produce a result for every possible input.