Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?


share|improve this question
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

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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.
share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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