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.

 

 

 

0Comment