Answer to Question #43231 in Math for Sujata Roy

Question

Which of the following problems is solvable?
a) Determining of an arbitrary turing M/c is a universal turing m/c
b) Writing a universal turing m/c
c) Determining of universal Turing m/c can be written in fewer than k instructions for some k.
d) Determining of universal turing machine and some input will halt.

Answer 1

Answer: b) Writing a universal turing m/c

Explanation: Every Turing machine computes a certain fixed partial
function from the input strings over its alphabet. In that sense it behaves
like a computer with a fixed program. However, as Alan Turing already
described, we can encode the action table of any Turing machine in a string.
Thus we might try to construct a Turing machine that expects on its tape a
string describing an action table followed by a string describing the input
tape, and then computes the tape that the encoded Turing machine would have
computed. As Turing showed, such a Turing machine is indeed possible and since
it is able to simulate any other Turing machine it is called a universal Turing
machine. With this encoding of action tables as strings, it becomes possible in
principle for Turing machines to answer questions about the behavior of other
Turing machines. Most of these questions, however, are undecidable. For instance,
the problem of determining whether a particular Turing machine will halt on a
particular input, or on all inputs, known as the Halting problem, was already
shown to be undecidable in Turing's original paper. Rice's theorem shows that
any nontrivial question about the behavior or output of a Turing machine is
undecidable.