Re: Attempt to Refute the Halting Problem's Refutation

From: Peter Olcott (olcott_at_worldnet.att.net)
Date: 08/19/04 

Date: Thu, 19 Aug 2004 00:58:42 GMT

<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

> 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

Relevant Pages

  • Re: PROOF that numbers are countable
    ... Well, all programs eventually *do* halt (when the power goes out, ... a series of symbols readable from and writable to tape. ... > We can get the UTM to run the UTM represented on the tape. ... >> usual proof of diagonalization doesn't quite work here, ...
    (comp.theory)
  • Re: Can a regular Turing Machine provide Protected Memory?
    ... >> but rather asks my UTM that is wrapping yours to get the result. ... > assume that everything is read from and written to the tape. ... >> input that has been designed to fool your halt analyzer. ... > I am not sure that I agree with this, but, can make it moot in any case. ...
    (comp.theory)
  • Re: Can a regular Turing Machine provide Protected Memory?
    ... >> but rather asks my UTM that is wrapping yours to get the result. ... > assume that everything is read from and written to the tape. ... >> input that has been designed to fool your halt analyzer. ... > I am not sure that I agree with this, but, can make it moot in any case. ...
    (sci.logic)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... >> the UTM to ask whether its thread of execution is looping? ... > All the halt analyzer asks the UTM is if there are any other ... > begin to do its halt analysis. ... or a variant of itself that alleges to solve the Halting Problem. ...
    (comp.theory)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... >> the UTM to ask whether its thread of execution is looping? ... > All the halt analyzer asks the UTM is if there are any other ... > begin to do its halt analysis. ... or a variant of itself that alleges to solve the Halting Problem. ...
    (comp.lang.cpp)