Some undecidable problems based on TM halting problem

1) The state entry problem :

Given a TM, a state q∈Q and w∈Σ+, decide whether or not the state 'q' is ever entered when M is applied to 'w'.This is undecidable.

 

2)Given a TM M,whether or not M halts if started with a blank tape,this is undecidable.

 

 

 

Contributor's Info

Created:
0Comment
Decidability Table for all language.

Decidability table for Regular ,Deterministic Context Free Language,CFL,CSL,Recursive and recursive enemurable language are as below:

 

Contributor's Info

Created:
0Comment
Decidable problem

A problem (p1) is said to be decidable if there exists an algorithm or a haulting turing machine for that problem.

Generally we decide whether the problem is decidable or not by comparing it with the other known problem(p2) whose decidability is known.

ie.. if there exists some algorithm or process by which (p1) can be converted to (p2) and it is well known about the decidability of the (p2) then we can say that problem (p1) is also decidable.

And we have to make sure that problem the result of (p1) = result of(p2)

This process can be extended to chain of problems.

All the problems in the chain has same result

Eg:  It is well known that Haulting problem in turing machine is un-decidable.

A haulting problem can be converted to post correspondence problem and post corresponcence problem is also undecidable.

In addition post correspondance problem can be converted to ambigious problem in context free grammers.

Therefore ambiguity problem in context free grammers is also undecidable.

 

Contributor's Info

Created:
0Comment