Re: Questions on turing machine problems

In article <3a3938dc-1cac-4dd4-b08a-7acecb9185b4@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
polymedes <polymedes@xxxxxxxxx> wrote:
On May 6, 10:27 pm, Tim Tyler <seemy...@xxxxxxxxxxxxxx> wrote:
If the machines are different, then the problem of whether they
write the same symbol at the same time can be transformed into
a halting problem - e.g. consider a third machine that simulates
the first two machines and halts iff the simulated machines
output the same symbol on their tapes at the same time.

This is a great answer! thanks for helping.

This reduction goes in the wrong direction. (The same error was made in
the original article---one wants a reduction *from* the halting problem,
not a reduction *to* the halting problem.)

However, it's easy enough to create a suitable reduction. Given a Turing
machine M, construct M1 and M2 as follows. M1 simulates M "silently,"
keeping track of exactly what M is doing but not actually sending M's
output to M1's own output tape. Instead, M1 outputs 0's until M halts,
and then it outputs 1's. M2, on the other hand, outputs 1's all the
time. If you could answer your question for the M1/M2 pair then you
could solve the halting problem for M.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • Re: Yet another Attempt at Disproving the Halting Problem
    ... >also proved that for certain, limited, machines, the halting problem ... Turing-complete, then sometimes the halting problem can solved ... diagonalization is more general than the halting problem. ...
    (comp.theory)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... >also proved that for certain, limited, machines, the halting problem ... Turing-complete, then sometimes the halting problem can solved ... diagonalization is more general than the halting problem. ...
    (comp.lang.cpp)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... >also proved that for certain, limited, machines, the halting problem ... Turing-complete, then sometimes the halting problem can solved ... diagonalization is more general than the halting problem. ...
    (sci.logic)
  • Re: Disproof of the Halting Problems Conclusion
    ... > Find me anywhere where it specifically states that the Halting Problem ... > is specifically limited to Turing Machines. ... Argh. ... > states that the solution set of the Halting Problem is limited to Turing ...
    (sci.logic)
  • Re: Disproof of the Halting Problems Conclusion
    ... > is specifically limited to Turing Machines. ... > states that the solution set of the Halting Problem is limited to Turing ... are equivalent in computing power. ...
    (sci.logic)