Rice's theorem states:
Every nontrivial property of recursively enumerable language is undecidable.
I came across following problems, which Ullman's books say both are undecidable:
- Turing machine accepts nothing. (empty language)
- Turing machine accepts something. (non empty language)
Consider we have given following TM (this I took from Mark's answer):
I want to decide whether the language of above TM is empty or non empty without actually running TM on any string, but "purely" by looking at TM description (consider above TM graph is input to below pseudo code in some encoded format. The encoded string contains information of everything: states, alphabet, allowed moves and transitions something like described in section 9.2.2 (page 63) of this pdf).
Step 1: Start from accept state and prepare breadth first tree (goal is to find all reachable nodes from accept state) rooted at accept state. It will look something like this:
--> q4 --> R --> q1 / / A --> q3 ----------> q2 --> q0
Now I know start state is contained in this tree. So, I know there is path from start state
q0 to accept state
Step 2: Read labels of edges on path in any order, from
A and come up with string that will be accepted by TM. Say we start from
q3 --[b/b,R]--> A
b. So last symbol of string will be
b(denote it as
b1as we will have more
b's in future).
Since this is acceptance state, ignore
q2 --[b/b,R]--> q3
We reach q3, reading
b. So second last symbol of string will be
b. (denote it as
Rmeans this second last symbol will be on left of last symbol:
q0 --[b/b,L]--> q2
We reach q2, reading
b. So third last symbol of string will be
b. (denote it as
b3). (Now lets assume algorithms do not allow moving to the left of first symbol of input string.)
Land start state
q0means dont do any movement of TM's read write head on tape. So,
Reached start state. So print the string which will be accepted by TM. So the string accepted will be
b2b1. Getting rid of symbol indices:
- Since TM accepts some string, its language is non empty.
Step 3: Try all paths between accept state
A and start state
q0, till we get at least one string accepted by given TM or till all paths are exhausted, in which case TM language will be empty.
We can run breadth first search to get all such paths.
I dont know if I am correct with above TM accepts string
bb, with assumption that we cannot move left to left most symbol of input string. But. I feel, below is instantaneous description of parsing
bb by this TM:
q0bb ⊢ q2bb ⊢ bq3b ⊢ bbA
Also I dont know if I am correct with above steps.
What I am trying to do is to come up with "generalized" steps which can be run on any TM description (not on tape content) to decide whether that TM accepts any string or not. This is because, if we can come up with such steps, then above two problems will turn decidable. I feel I am missing something in all these efforts which is preventing me from realizing why these languages cannot be turned decidable by any such reverse engineering efforts.
Earlier doubt which is currently more refined / rephrased / reworded above, but kept below for reference:
Consider we have given description of TM in encoded format. The encoded string contains information of everything: states, alphabet, allowed moves and transitions something like described in section 9.2.2 (page 63) of this pdf). Then cant we have a Turing Machine which will parse the code describing TM and decide whether it accepts anything or nothing. For example, find final state in the code and then go through all encoded transitions in reverse order starting from final state and check if we reach starting state. This can be done by forming MST rooted at final state. If MST contains starting state, then TM accepts something else it does not accept anything.
Note that I am talking about parsing TM description not tape content and since TM description (and number of transitions) is finite (correct me if TM description can be infinite) we can form MST in finite time.
I feel I am missing something stupid here, since if this proves its decidable whether TM accepts nothing or something, then I believe, it will be really a big thing in computer science (may be it will imply some problems previously believed to be undecidable to be decidable). What is that thing which I am missing?