World's most popular travel blog for travel bloggers.

[Answers] How to I get a TM with lowest index?

, , No Comments
Problem Detail: 

I'm struggling to understand this question:

Give an encoding of the Turing machine with lowest index that accepts anything but the empty set.

I know what an encoding of a Turing Machine is. But my professor didn't explain what the index of a Turing machine is and how I know that it is lower or higher? Can someone explain what lowest index is and how would I go about this problem?

Asked By : flashburn

Answered By : Ran G.

If I understand your question correctly, then it simply asks for the TM with the encoding who is ordered first in the lexicographic ordering.

As you surely know, many TMs perform the same task. Look at all the TMs that accept anything but empty set. Look at the encodings of all of those. Each encoding is simply a string. If you write all those string ordered using the lexicographical ordering (like in the dictionary), which string comes first? That should be your answer.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback