Re: Attempt to Refute the Halting Problem's Refutation

newstome_at_comcast.net
Date: 08/15/04 

Date: Sun, 15 Aug 2004 04:05:00 GMT

In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:

> No TM that writes a 1 to its tape for halting or a zero for not
> halting can do this for the universal set of TMs.
>
> TM = The universal set of Turing Machines.
> SIGMA = The universal set of input strings .
>
> There does not a exist Turing Machine H, such that for all M in TM
> and for all W in SIGMA such that H(M,W) writes a ONE if M halts
> on W and a ZERO if M does not halt on W to a specific location on
> the tape of H.

Excellent. I'm happy to take your statement here. To keep everything
straight, I'll add a new point in each posting, and at the bottom of
each posting include a summary of everything we've established so far.

Now, you want a way of providing "write-only" output. Let's make
something called "Peter's TM" (or PTM) that has an extra tape that is
write-only. The PTM has no ability to read from this tape at all. A
"user" can see the result, but no program on the PTM can access the
result. This is a simple model to make -- the transition function
simply maps f(s,t) -> (ns,nt,tm,ot,om) where s and t are the state and
tape symbols in the current state, ns,nt,tm are the new state, new
tape symbol, and tape movement, and ot is the output tape symbol to
write and om is the motion for the output tape.

Since f doesn't depend on the output tape at all, the output tape
can't affect the computation in any way, so is truly write-only.

Is this a sufficient model, with the write-only tape, that you believe
a solution to the halting problem on this model could exist (writing
its output to the write-only tape)?

========================================================================

Summary of things before this posting.

Definitions:
  1) The "halting problem" takes a machine M and input x and decides
     whether or not M halts when started with input x
  2) An algorithm/program "solves the halting problem" if it correctly
     decides the halting problem for all input pairs (M,x)

Logic:
  1) FACT: There does not exist a Turing machine that writes a ONE or
     ZERO to a specific location on its tape to denote halts/doesn't
     halt (solving the halting problem). 

-- 
That's News To Me!
newstome@comcast.net

Relevant Pages

  • Re: Turing computable function
    ... iff there is a Turing machine T with an input and with an output tape ... such that if you write an element x of X on the input tape, ... your Turing machine that computes f has a specific defined behavior only ... that a TM that computes f must loop when it's input is not in X. ...
    (comp.theory)
  • Re: Alan Turings Halting Problem is Incorrect (FINAL PART)
    ... > this question (to fully solve the Halting Problem) would require ... two parameters on its tape (separated by an agreed-upon ... The second is a number encoding ... if it sees a "1" in the first cell of the tape, ...
    (sci.logic)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... "a Turing machine", is to remove extrania from the ... its tape. ... the solvability of the Halting Problem. ... But, don't go looking at that formal definition, ...
    (comp.theory)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... "a Turing machine", is to remove extrania from the ... its tape. ... the solvability of the Halting Problem. ... But, don't go looking at that formal definition, ...
    (sci.logic)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... > There does not a exist Turing Machine H, such that for all M in TM ... > the tape of H. ... write and om is the motion for the output tape. ... The "halting problem" takes a machine M and input x and decides ...
    (comp.theory)