UNIT-5

Church- Turing Thesis

• In computability theoryIn computability theory, the Church–Turing thesis is a thesisIn computability theory, the Church–Turing thesis is a thesis about the nature of computable functions.
• The Church-Turing thesis says that every solvable decision problem can be transformed into an equivalent Turing machine problem.
• To say that the Turing machine is a general model of computation means that any algorithmic procedure that can be carried out at all, by a human computer or a team of humans or an electronic computer, can be carried out by a TM.

• The theorem states that TM’s compute exactly same things that computers compute.
• In other words we can say, “no computational procedure will be considered as algorithmic procedure unless it can be represented using Turing Machine”.
• Unfortunately, this Thesis cannot be proven, but it is believed in the basis of amount of evidence that support it.
• Because, just it is an idea or statement that cannot be derived from logical statements.

​

​

​

Universal Turing Machine

• TMs are mathematical models of general purpose computers and we are aware that computers are not designed to solve specific problems, they simply execute program instructions stored in their memory, based on the algorithm for any data.
• But, TMs so far we discussed are ‘unprogrammable’ devices solved to specific problem.
• But, is any possibility to convert a TM into programmable general purpose computer.

• Such general purpose TMs are called universal Turing Machines.

Definition: A Universal TM Tu takes two arguments:

1. The description of computation i.e. TM
2. The Input String

​

Universal Turing Machine

• Universal TMs are extremely powerful and have enough power to simulate the behavior of any TM.

Diagonalization Language

• The language, that is not accepted by any Turing machine is called Diagonalization language.
• Means, Diagonalization languages are non-recursive enumerable languages.
• The diagonalization language Ld, is the set of strings of Wi, where Wi is not in L(Mi).

​

Universal Language

• The Universal Language Lu is the set of binary strings that encode a pair <M,w> where w is accepted by M.
• Turing Machine M, is going to accept any type of languages over an specific input alphabets.
• To accept any type of languages, we require universal Turing machine.
• The universal language L_u is a recursively enumerable language.

Rice’s Theorem

• A property is called to be trivial if either it is not satisfied by any recursively enumerable languages, or if it is satisfied by all recursively enumerable languages.
• The two Trivial Properties are Decidable i.e. either none or all.

​

• Rice theorem states that any non-trivial property of a language which is recognized by a Turing machine is undecidable.

Formal Definition

• If P is a non-trivial property, and the language holding the property, L_p , is recognized by Turing machine M, then L_p = {<M> | L(M) ∈ P} is undecidable.

​

• A non-trivial property is satisfied by some recursively enumerable languages and are not satisfied by others.
• In a non-trivial property, where L ∈ P, both the following properties hold:
• Property 1 − There exists Turing Machines, M1 and M2 that recognize the same language, i.e. either

( <M1>, <M2> ∈ L ) or ( <M1>,<M2> ∉ L )

• Property 2 − There exists Turing Machines M1 and M2, where M1 recognizes the language while M2 does not, i.e. <M1> ∈ L and <M2> ∉ L

​