Re: What is the Result from Invoking this Halt Function?
From: Will Twentyman (wtwentyman_at_read.my.sig)
Date: 08/11/04
- Next message: peter_douglass: "Re: Rado's Sigma and the Halting Problem for Programs"
- Previous message: r.e.s.: "Re: Rado's Sigma and the Halting Problem for Programs"
- In reply to: Peter Olcott: "Re: What is the Result from Invoking this Halt Function?"
- Next in thread: Peter Olcott: "Re: What is the Result from Invoking this Halt Function?"
- Reply: Peter Olcott: "Re: What is the Result from Invoking this Halt Function?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Wed, 11 Aug 2004 15:51:56 -0400
Peter Olcott wrote:
> "Will Twentyman" <wtwentyman@read.my.sig> wrote in message news:4118e82c$1_5@newsfeed.slurp.net...
>
>>Peter Olcott wrote:
>>
>>
>>>"Marc Goodman" <marc.goodman@comcast.net> wrote in message news:U_XRc.277260$Oq2.198273@attbi_s52...
>>>
>>>
>>>>Peter Olcott wrote:
>>>>
>>>>
>>>>>>Isn't it about time you started to read Turing's proof so you can
>>>>>>pinpoint the exact line which is in error?
>>>>>
>>>>>It looks like the error is in its application to the Halting Problem.
>>>>>I did print it out. There is some material that is interesting and easy.
>>>>
>>>>So, Peter, just to make sure I understand...
>>>>You now say that since your refutation of Turing's proof does
>>>>not actually apply to Turing's proof, that it's because Turing's
>>>>proof has been erroneously applyed to halting problem? Or, your
>>>
>>>
>>>It looks like Turing's proof may be erroneously applied to the
>>>Halting Problem. It looks like Turing might have assumed that
>>>the Halt function must always return a result to all callers.
>>
>>That is basically what the Halt function is *defined* to do. "return a
>>result to all callers," is not how it is normally defined, but that is a
>>fairly good description of the required behavior.
>
>
> How about this?
>
> A halt function that correctly determines whether any element in the
> universal set of Turing Machines will execute in a finite number of
> steps for any specific input data.
>
> This one is no longer impossible. I will update my website
> very soon, and provide a good write-up of this much simpler
> proof.
I'll save you some effort:
[begin quote from www.halting-problem.com]
;Disproving the Halting Problem
;
;Quick Summary:
;Alan Turing conclusively proved is that it is impossible to construct a
;halt analyzer that always returns a correct result back to the program
;being analyzed.
;
;Since returning the result back to the program being analyzed is not
;the only way to construct a halt analyzer, his proof did not show that
;constructing a halt analyzer that works correctly for all input is
;impossible.
;
;Definition of the Halting Problem
;There does not exist a Turing Machine that can correctly determine
;whether or not each and every element in the universal set of Turing
;Machines will execute in a finite number of steps.
;
;Basis of this Informal Proof
;Simply refrain from returning the results of the Halt function to any
;other Turing Machines. In order to return results there must be a
;calling convention. In this case the return value can be placed in a
;certain fixed location on the Universal Turing Machine's tape. Many
;other calling conventions are possible.
;
;When the return value of boolean TRUE is indicated (that the TM will
;halt) a ONE is placed in this fixed tape location. This leaves a ZERO
;for FALSE (does not halt), and the SPACE can be used to indicate that
;no value is being returned. Other values can be substituted if desired.
;
;The last step is the method by which the Halt function can determine
;its calling context. In other words whether or not it was called by
;another Turing Machine, or invoked independently of any other Turing
;Machine.
;
;This can be a very simple feature that is implemented in the Universal
;Turing Machine. The Halt function would merely ask the UTM whether or
;not its specifically indicated final state has any state transition
;defined. This information is very easy for the UTM to provide, it
;merely looks up the action associated with the state in its state
;transition matrix table. If there is no state transition defined out of
;the Halt function's final states, then the Halt function can know with
;certainty that it was not invoked as a part of another Turing Machine's
;execution. It can use this information to determine whether or not it
;can safely return a result, or that it must refrain fro returning a
;result.
;
;If these steps are taken, then the counter-example Turing Machine that
;has been used as the basis for contructing the Halting Problem Proof
;can no longer have any effect of the Halt analyzer or its ability to
;produce correct results for each element of the universal set of Turing
;Machines.
[end quote]
This is riddled with errors from beginning to end.
First of all, you clearly do not understand what a TM is. A Turing
Machine is a set of instructions for a read/write head over an
infinitely long piece of tape divided into cells which are either marked
or blank. It is generally represented as a state machine, with each
state acting to optionally mark/erase the current cell, move left/right
one cell, and change to a new (possibly different) state.
A given TM is started in a start state over the tape with finitely many
of the cells marked. It then moves through various states until it
reaches a halting state (which may or may not happen). The original
marking of cells is the input, the final marking of cells when it halts
is the output.
A UTM is a TM that uses an encoding of another TM and the encoded TM's
input as the UTM's input. How this is done depends on the particular
UTM. The UTM then emulates the encoded TM and produces the TM's output
on the encoded input. In otherwords: UTM(<TM>,<input>) = TM(input)
where <TM> is the encoding of TM, and <input> is the encoding of input.
For a UTM to work correctly, it must produce exactly the same output
that TM would as an independent machine.
A halt analyzer is a Turing Machine that accepts as its input
<TM>,<input>, always halts, and produces output indicating (correctly)
whether TM(input) halts. Call this machine HALT.
Here is where your analysis begins to fail. First, HALT may or may not
be running on a UTM. If it is not running on a UTM, it cannot query the
UTM. Second, HALT does its processing bases only on its input. Context
is meaningless because there is only one context, the machine itself.
If it is being emulated on a UTM, that fact cannot affect its results or
you are not emulating HALT. HALT does not have three possible outputs.
It has two possible outputs <TM(input) halts> and <TM(input) does not
halt>. The method of encoding those outputs is irrelevant.
If you make the modifications that you propose, several things result:
First, you are no longer discussing the Halting Problem.
Second, you are no longer discussing UTMs.
Third, any conclusions you draw from the new situation are unrelated to
the Halting Problem.
You have talked about the fact that you are a programmer. Surely, as a
programmer, you are aware of the fact that when you are asked to
construct something, it must behave in a specified way. For example, a
stack must provide the functionality push() and pop() at the very least.
If you are told what push() and pop() are supposed to do as your part
of a larger program, you cannot *change* that behavior to suit your
purposes. If you do, the work others will be doing will be incorrect.
The bug lies in your change, not in their work. The same is true here.
You cannot change the behavior of things and claim they have anything
to do with what is originally specified.
-- Will Twentyman email: wtwentyman at copper dot net
- Next message: peter_douglass: "Re: Rado's Sigma and the Halting Problem for Programs"
- Previous message: r.e.s.: "Re: Rado's Sigma and the Halting Problem for Programs"
- In reply to: Peter Olcott: "Re: What is the Result from Invoking this Halt Function?"
- Next in thread: Peter Olcott: "Re: What is the Result from Invoking this Halt Function?"
- Reply: Peter Olcott: "Re: What is the Result from Invoking this Halt Function?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
