Re: Attempt to Refute the Halting Problem's Refutation

newstome_at_comcast.net
Date: 08/19/04 

Date: Thu, 19 Aug 2004 01:49:37 GMT

In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:
>
> <newstome@comcast.net> wrote in message news:ipJUc.320007$JR4.161067@attbi_s54...
>> In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:
>
>> We need at least one more definition in order to get to your
>> argument. You're using a non-standard UTM, so let's define that:
>>
>> A PUTM (Peter's UTM) is a standard UTM that can also give
>> information about the program running on it to the program (in other
>> words, "introspection"). To be specific, a program can ask a PUTM
>> to give it a description of the entire program being run on it,
>> which results in the state transition table of the program being
>> written to the tape. This way a program can test if it's being run
>> alone or as part of a larger program. Like a regular UTM, the input
>> to a PUTM is a <machine,input> pair, telling the PUTM what program
>> to run.
>
> No this is not it. Its more like this.
>
> // Here is the UTM function header
> //
> int ThereAreTransitionsOutOfThisState(int StateNumber)
> {
> if (StateTransitionMatrix[StateNumber] == STATE_TRANSITION)
> return 1;
> else
> return 0;
> }
>
> // Here is the halt analyzer using this function
> //
> if (ThereAreTransitionsOutOfThisState(HaltAnalyzerFinalState))
> return;
> else
> // Analyze the input TM and write a ONE to the tape it it halts
> // or a ZERO to the tape if it fails to halt

This is very imprecise since your "ThereAreTransitionsOutOfThisState"
function returns information to the UTM at the request of the UTM. If
you want the program *run* by the UTM to be able to query this
information, then you have to specify how that works.

You can do this with the definition I gave above, and accomplish
exactly what you want to accomplish. I will not require you to take
my definition, since it's your argument, but here's how my definition
works with your argument: If you have a halt analyzer, say a function
PHA(machine,input) [PHA is "Peter's Halt Analyzer"], then the first
thing it can do with my definition of a PUTM is to ask for the state
transition table -- it can then compare this with what it knows PHA is
to determine if there is anything at all other than PHA being run. If
anything else is there, it halts without giving an answer. Only if it
is run completely by itself in the PUTM then will it give a ONE or
ZERO answer. This way, if PHA is called from WillHalt, it will not
return a value, so WillHalt doesn't have anything to work with, so we
can't make the standard contradiction. That's the gist of your
argument, right?

Again, I don't want to force you into using my definition, but that's
my explanation of how it will support your argument. If you don't
like my definition, then feel free to give a decent definition. But
you must show how a program fun on the PUTM can make this special
query and use its results, so what you've written above isn't a valid
definition. The program must be able to do the query, not the PUTM
(which will supply the answer to the program), because the PUTM has no
purpose other than to run the program.

>> Is that a good enough model for you to construct your halt analyzer?
>>
>> ========================================================================
>>
>> 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)
>>
>> --
>>
>> That's News To Me!
>> newstome@comcast.net
>
> 

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

Relevant Pages