Session 4: �Universal TM

By

Dr. Ashok Kumar

Amity School of Engineering & Technology

Turing Machines are “hardwired”

they execute

only one program

A limitation of Turing Machines:

Real Computers are re-programmable

Amity School of Engineering & Technology

Solution:

Universal Turing Machine

• Reprogrammable machine

​

• Simulates any other Turing Machine

Attributes:

Amity School of Engineering & Technology

Universal Turing Machine

simulates any other Turing Machine

Input of Universal Turing Machine:

Description of transitions of

Initial tape contents of

Amity School of Engineering & Technology

Universal

Turing

Machine

Description of

Tape Contents of

State of

Three tapes

Tape 2

Tape 3

Tape 1

Amity School of Engineering & Technology

We describe Turing machine

as a string of symbols:

​

We encode as a string of symbols

Description of

Tape 1

Amity School of Engineering & Technology

Alphabet Encoding

Symbols:

Encoding:

Amity School of Engineering & Technology

State Encoding

States:

Encoding:

Head Move Encoding

Move:

Encoding:

Amity School of Engineering & Technology

Transition Encoding

Transition:

Encoding:

separator

Amity School of Engineering & Technology

Machine Encoding

Transitions:

Encoding:

separator

Amity School of Engineering & Technology

Tape 1 contents of Universal Turing Machine:

​

encoding of the simulated machine

as a binary string of 0’s and 1’s

Amity School of Engineering & Technology

A Turing Machine is described

with a binary string of 0’s and 1’s

The set of Turing machines forms a language:

each string of the language is

the binary encoding of a Turing Machine

Therefore:

Amity School of Engineering & Technology

Language of Turing Machines

L = { 010100101,

​

00100100101111,

​

111010011110010101,

…… }

(Turing Machine 1)

(Turing Machine 2)

……

Amity School of Engineering & Technology

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.

Amity School of Engineering & Technology

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.”

Or in simple words we can say that “Every computation that can be carried out in the real world can be effectively performed by a Turing Machine.”

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.

​

Amity School of Engineering & Technology