Can the Turing machine be classified e.g. as a Mealy machine? Why not? Can a Turing machine be input to another Turing machine without complication like halting problems?


  • 1
    Hi, since this is a purely theoretical question I think it can be better answered on Computer Science. – K.Steff Jun 21 '12 at 10:08

For your first question, consider, for example, Wikipedia's formal definition of a Mealy machine. Your question is precisely equivalent to "can a Turing machine be described in terms of that definition?" Looking at a formal definition of a Turing machine would be instructive.

For your second question, you may want to research Universal Turing Machines. They are a formulation of nearly exactly the idea of "inputting a Turing machine into another Turing machine", and any reasonable resource that discusses those more than in passing will certainly help give you some idea of how the halting problem relates to them.


This sounds awfully like some homework, so I'll refrain from giving a more detailed answer, but considering inputting a Turing machine:

  • You can encode every Turing machine into a string (read up on Gödel numbers on that)
  • The halting problem only ever becomes a problem at all, if a Turing machine is simulated/running in some way.
  • When you input a string into another Turing machine, the string may encode a Turing machine, but no one says that it has to execute this Turing machine. So your second question is essentially pointless, as you can obviously input a string to a Turing machine.
  • 4
    Does it matter if its a homework question or not? If its a valid question and not a duplicate than a detailed answer is still valuable – Tom Squires Jun 21 '12 at 8:29

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