0
$\begingroup$

When we talk about the enumeration of TM's, do we mean the "regular" deterministic ones? So if we want to enumerate nondeterministic or probabilistic TM's, do we need a separate enumeration?

I can see how we could describe probabilistic TM's as strings, just as we describe the deterministic TM's only now we have two transition functions. Then it also follows that checking whether some string enumerates a probabilistic TM is decidable. Perhaps one could think of a way to create some universal coding of TM's to strings that works for all different kinds of TM's? Perhaps the first ... digits of the enumeration describe what kind of TM (probabilistic, determinstic etc) it is and then follows the description of the TM in the standard fashion. So then we can enumerate all the TM's?

A related question, does a TM know it's own description? Or can we give it that information without loss of generality?

$\endgroup$
0
$\begingroup$

When we talk about the enumeration of TM's, do we mean the "regular" deterministic ones?

We mean an enumeration of whatever kind of Turing machines we're talking about at the moment. Unless stated otherwise, "Turing machine" is normally taken to mean deterministic Turing machine.

Perhaps one could think of a way to create some universal coding of TM's to strings that works for all different kinds of TM's?

There's no fixed list of "all different kinds of TM's", so I don't see how this would be possible.

A related question, does a TM know it's own description?

It's not clear to me what it means for a TM to "know" anything. A Turing machine is just its state set, transition function and so on.

$\endgroup$

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.