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,....}

Comments

DESIGN TM FOR {a^n b^n c^n | n>=1}

Concept:- General_idea: click_me L={a^n b^n c^n | n>=1} w={abc,aabbcc,aaabbbccc,....} a a a b b b c c c X a a Y b b Z c c X X a Y Y b Z Z c Step_1: Replace a by X and go right side. TM tape can move any side. It has infinite memory in both side. And it can remember previous states details. Step_2: Replace b by Y and go right side of tape. Step_3: Replace c by Z and turn left till X . Step_4: After seeing X(capital X) replace next a by X and do same loop. Step_5: X portions finished. Step_6: Move to Y states. Denote it for one move first and after that notate self loops. Goto final state Z in self loop. Finally stop turing machine. Success. Next step: How to add self loop states? Ok listen me... For that we are taking two steps X a a Y b b Z c c X X a Y Y b Z Z c Just understand in between symbols. And make it as self loops. If any doubt please post comments..I can explain it. Small editing...This one...

PCP & MPCP

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.

Restricted Turing machine

1)Linear Bounded Automaton 2)Multi-stack Machines 3)Counter Machines 4)Limits on the number of states and symbols Explanation: 1)Linear Bounded Automaton: is a type of turing machine wherein the tape is not permitted to move off the portion of the tape containing the input. If the machine tries to move its head off either end of the input,the head stays where it is,in the same way that the head will not move off the left-hand end of an ordinary turing machine's tape. A Linear bounded automaton is a TM with a limited amount of memory. It can only solve problems requiring memory that can fit within the tape used for the input. Using a tape alphabet larger than the input alphabet allows the available memory to be increased up to a constant factor. 2)Multi-stack Machines: A deterministic two-stack machine is a deterministic TM with a read only input and two storage tapes...

Theory Of Computation

Search This Blog