Skip to main content

13/11/2012

Clique in an undirected graph is a subgraph, wherein every 2nodes are connected by an edge.

Clique Problem is to determine whether a graph contains a clique of specified size.

Satisfiability Problem is to test whether a boolean formula is satisfiable. Boolean formula is an expression involving boolean variable & operations. 

Halting Problem is the problem for determining whether a turing m/c halts(by accepting/by rejecting) on a given input.

Decidable  is a problem whose language is recursive. 

A problem is undecidable if there exist no algorithm that takes as input an instance of the problem and determine whether the answer to that instance is "yes" or "no".

Halting Problem is undecidable theorem and proof's scanned copy will upload next day. 

Church's Thesis: - What function cant be computed by turing machines? This is very surprising. It is believed that there are no functions that can be defined by humans,whose calculation can be described by any well defined mathematical algorithm that people can be taught to perform,that cant be computed by TMs. The TM is believed to be the ultimate calculating mechanism. 
Church actually said that any machine that can do certain list of operations will be able to perform all concievable algorithms. he tied together what logicians had called recursive functions and computable functions. TMs can do all that Church's asked, so they are possible model of the universal algorithm machine Church described.

Listen students......
Chomsky Classification/Hierarchy is not equal to Chomsky Normal Form. I will upload some notes about that next day.

Comments

  1. Arun Anoop MNovember 14, 2012 at 4:21 AM

    I had posted the same things in Our students google groups corner...

    MESCE CSE A '10 - '14

    ReplyDelete

Post a Comment

Popular posts from this blog

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...
Post a Comment
Read more

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 ......
6 comments
Read more

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.
Post a Comment
Read more