Re: Attempt to Refute the Halting Problem's Refutation

newstome_at_comcast.net
Date: 08/19/04 

Date: Thu, 19 Aug 2004 03:40:57 GMT

In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:
> <newstome@comcast.net> wrote in message news:RGTUc.185717$eM2.167175@attbi_s51...
>> In comp.theory Peter Olcott <olcott@worldnet.att.net> wrote:
>
>> > 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
>
> No it does not.

[ Pissy part of reply cut. I've been very patient with your poor
explanation skills and have remained civil. It looks like I did miss
something above, so it would certainly be nice if you could show some
patience and civility as well. ]

OK, yes I missed something. I see that you're saying you can call the
UTM function directly from the halt analyzer. You don't say how this
is done in a TM (which has no standard notion of calling a function),
but this is OK for now. You also assume that the halt analyzer knows
some identifier for its final state ("HaltAnalyzerFinalState"), but
this is pretty easy to handle as well. So let me change the
definition of a PUTM to account for this, and see if you agree with
this:

  A PUTM is a universal TM in which a subroutine can be defined in
  such a way that (a) the subroutine is given an identifier that
  uniquely identifies the final state of the subroutine and (b) the
  subroutine can query the PUTM to see if there are any transitions
  out of this state.

How's that?

>> 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
>
> 

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

Relevant Pages

  • Re: Attempt to Refute the Halting Problems Refutation
    ... >> A PUTM is a standard UTM that can also give ... 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 ...
    (comp.theory)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... >> A PUTM is a standard UTM that can also give ... 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 ...
    (sci.logic)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... > function returns information to the UTM at the request of the UTM. ... > thing it can do with my definition of a PUTM is to ask for the state ... This way, if PHA is called from WillHalt, it will not ... The program must be able to do the query, ...
    (comp.theory)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... > function returns information to the UTM at the request of the UTM. ... > thing it can do with my definition of a PUTM is to ask for the state ... This way, if PHA is called from WillHalt, it will not ... The program must be able to do the query, ...
    (sci.logic)
  • Re: Attempt to Refute the Halting Problems Refutation
    ... >> function returns information to the UTM at the request of the UTM. ... A PUTM is a universal TM in which a subroutine can be defined in ... >> query and use its results, so what you've written above isn't a valid ...
    (comp.theory)