-2
$\begingroup$

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:

  1. Turing machine accepts nothing. (empty language)
  2. Turing machine accepts something. (non empty language)

Doubt

Consider we have given following TM (this I took from Mark's answer):

enter image description here

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

Step 2: Read labels of edges on path in any order, from A to q0 or q0 to A and come up with string that will be accepted by TM. Say we start from A.

  • q3 --[b/b,R]--> A
    We reach A, reading b. So last symbol of string will be b (denote it as b1 as we will have more b's in future).
    Since this is acceptance state, ignore R.
  • q2 --[b/b,R]--> q3
    We reach q3, reading b. So second last symbol of string will be b. (denote it as b2). R means this second last symbol will be on left of last symbol: b2b1
  • 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.) L and start state q0 means dont do any movement of TM's read write head on tape. So, b3=b2.

  • 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: bb

  • 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?

$\endgroup$
4
$\begingroup$

You said in a comment:

I am talking to process this encoding, not the tape content.

But the tape content affects the behavior of the TM, including whether it would enter an accepting state. The exact same TM in the exact same state might later accept, or not accept, depending only on what is on the tape.

You want to "go through all encoded transitions in reverse order", but the behavior of the transition function depends on what is on the tape. You can't run the transition function, either forward or backward, without keeping track of what is on the tape. But you say you're not keeping track of that.


I am not able to convince you in the comments that you need to keep track of the tape, so perhaps you can convince yourself. Here are four Turing machines. Their tapes should initially contain sequences of a and b with only a finite number of a, because b represents blank.

In each machine, the initial state is $q_0$, state $A$ is an accepting state, and all the other states are rejecting states. To help you, I will point out that the machines differ only in what they print on the tape in the transitions $q_0\to q_2$ and $q_1\to q_2$. They are otherwise identical.

Each of these machines will either accept every input, reject every input, or accept some inputs and reject some inputs. I will not tell you which is which, but I assure you that not all four machines are of the same type.

Your job is to use your static MST method to decide which is which, without considering the possible contents of the tapes.

Good luck.

enter image description here enter image description here enter image description here enter image description here

$\endgroup$
  • $\begingroup$ I guess its wrong to say "transition function depends on what is on the tape". Someone CAN give us TM description and no tape content. So the transition functions are already given to us through TM description without telling tape content to operate TM on. In other words, transition functions are defined independently of tape content. Same person might give us tape content in future and ask us to run TM on it, in which case "transitions followed" will differ for different content. But transition definitions are still the same. $\endgroup$ – anir Nov 16 '19 at 15:20
  • $\begingroup$ You're right. It's the behavior of the transition function that depends on the content of the tape. But I think the behavior is just what you propose to track. I have corrected the wording of my answer. $\endgroup$ – Mark Dominus Nov 16 '19 at 15:22
  • $\begingroup$ Yes & No. I was not proposing to track behavior of transitions "for some tape content" but evaluate behavior specified by their definition. For example, consider the TM graph given in figure 6.2 or 6.3 of page 47 of this pdf. Note that transitions are defined in this figure independent of tape content. I was saying deciding whether these TMs accepts nothing or something will involve travesing graphs (independent of any tape content) in these figure to form MST rooted at accepting state and check if that MST contains start state. $\endgroup$ – anir Nov 16 '19 at 15:25
  • 1
    $\begingroup$ "We can simply concatenate those tape symbols to form input string which will take that path" No, it won't; the machine can move left and then it won't see the "next" symbol. $\endgroup$ – Alexey Romanov Nov 16 '19 at 20:32
  • 1
    $\begingroup$ Was really good exercise!! It made me realize that guessing string accepted by TM is not as easy as forming MST & concatenating its edge labels. I was completely ignoring left right movements. I have to agree its very difficult to figure out language accepted by TM given information of its transitions. I gave some try. I might not be fully correct. But at least I was able to figure out that first two dont accept anything & last two accept strings of form b(aa)*b, that too just looking at transitions & logically interpreting them to come up with acceptable strings. [continued...] $\endgroup$ – anir Nov 16 '19 at 21:19
2
$\begingroup$

Because this process doesn't necessarily end; you can end up discovering more and more possible configurations (state+tape) which would lead to accepting if they were ever reached, but never a legal initial configuration.

$\endgroup$
  • $\begingroup$ "lead to accepting if they were ever reached". I am talking to start from accepting state and traverse transitions in reverse order to reach start state. Its like forming spanning tree on TM transitions with accepting states as a root and then check if spanning tree contains start state. I guess algorithm forming spanning tree wont run forever, right? Do I make sense? Or sound confusing? (I know I am asking somewhat more fundamental question, "why rice theorem works" if what I explain is correct. I feel I am missing something.) $\endgroup$ – anir Nov 16 '19 at 13:18
  • $\begingroup$ @anir: the state of a computation includes the entire tape. So there is an unlimited number of states to investigate. $\endgroup$ – rici Nov 16 '19 at 14:16
  • $\begingroup$ "unlimited number of states"? I guess I was not able to convey what I mean clearly. Consider problem "given TM accepts nothing". We are given description of TM as encoded string which contains everything in encoded format: states, alphabet, allowed moves & transitions as explained in section 9.2.2 (page 63) of this pdf. I am talking to process this encoding, not the tape content. I hope this TM description code is finite in length and number of transitions is also finite. If yes, we can form MST in finite time. Am I missing anything? $\endgroup$ – anir Nov 16 '19 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.