Skip to main content

Godelization in Turing machine

godelization is a encoding technique which encodes a string as a number. This is known as Godel numbering.


Popular posts from this blog

Design a TM(Turing Machine) , L={a^nb^n | n>=1}

Design View:

By JFLAP Software

Concept : 
aaabbb Case1: XaaYbb Case2:XXaYYb Case3:XXXYYY

Case 1: Read first 'a' and replace it by 'X' Then read first 'b' and replace it as 'Y'
What i am doing is .....Meaning of a^n b^n is " Equal no: of a's must followed by equal no: of b's " In Case 1 : I read first 'a' and First 'b'.
Before reading Second 'b'....Should read Second 'a' ....
Then continue the steps.....Finally 'B' reads....Machine will stop...

Transitions concept will continue ......


PCP(Post's Correspondence Problem)MPCP(Modified PCP)
PCP consists of two lists A=w1,....,wk and B=x1,....,xk , of strings over some alphabets SIGMA. This instance of PCP has a solution if there is any sequence of integers i1,i2,.....,im,with m>=1. Such that
wi1,wi2,....,wim=xi1,xi2,....,xim. The sequence i1,....,im is a solution to this instance of PCP.
MPCP  Lists A & B of k strings each from Sigma*.say A=w1,w2,...,wk and B=x1,x2,.....,xk does there exist a sequence of integers i1,i2,....,ir. such that w1 wi1 wi2 .... wir=x1 xi1 xi2 ..... xir ?
Difference between PCP and MPCP is that in the MPCP, a solution is required to start with the first string on each list.

Partial recursive function

Partial recursive function
are turing computable. It means that there exist a turing machine TM for every partial recursive function.

Recursion: A function which calls itself directly or indirectly and terminates after finite number of steps is known as recursive function.

In recursive functions,terminating point is known as base point.

A function is called partial recursive if it is defined for some of its arguments. 
Let   f(a1,a2,....,an) is a function and defined on function     g(b1,b2,....,bm) , then f is a partial function if some elements of     f  is assigned to almost one element of function   g.

A partial function is recursive if
i)It is an initial function over N, or
ii)It is obtained by applying recursion or composition or minimalization on initial function over N.

'N' Natural numbers  {0,1,2,....}