Total recursive function

Total recursive function

All those partial functions for which turing machine halts are called total recursive functions.

From the definition of both it is clear that total recursive function is the subset of partial recursive function.

A total function is a subclass of partial function.

A function is called total function if it is defined for all its arguments.

Let f(a1,a2,....,an) be a function and defined on function g(b1,b2,....,bm), then f is a total function if every element of f is assigned to some unique element of function g.

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

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

Theory Of Computation

Search This Blog