1. Forum
  2. Usenet
  3. SCI.LOGIC

  • Re: Correction to of the error in the halting problem specification

    From Mikko@21:1/5 to Graham Cooper on Sun Jan 14 12:46:12 2024
    On 2024-01-14 07:42:01 +0000, Graham Cooper said:

    On Sunday, January 14, 2024 at 6:31:19 PM UTC+11, immibis wrote:
    On 1/14/24 01:22, olcott wrote:> > In computability theory, the halting
    problem is the problem of> > determining, whether an input finite
    string pair of program/input> > specifies a computation that would
    reach a final state and terminate> > normally.> >> > 01 int D(ptr x)
    // ptr is pointer to int function> > 02 {> > 03 int Halt_Status =
    H(x, x);> > 04 if (Halt_Status)> > 05 HERE: goto HERE;> > 06
    return Halt_Status;> > 07 }> >> > The input to H(D,D) specifies that D
    calls its own termination> > analyzer as a part of this computation.
    The prior definition> > of the halting problem allowed people to
    incorrectly ignore this.> >> > A decider computes the mapping from its
    input...> > *The prior definition of the halting problem ignored this*>

    your definition still ignores it


    halt is DEFINED to input a PROGRAM identifier

    No, not a program identifier but a complete description of the
    program and an input, i.e., an input that some universal Turing
    Machine accepts.

    Mikko

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mikko@21:1/5 to olcott on Sun Jan 14 12:42:21 2024
    On 2024-01-14 00:22:10 +0000, olcott said:

    In computability theory, the halting problem is the problem of
    determining, whether an input finite string pair of program/input
    specifies a computation that would reach a final state and terminate normally.

    The definition of the halting problem does not specify "normally".
    Termination just means a situation where continuation is not possible. Non-termination means that such situation does ever occur even when
    the program runs forever.

    There is no error in the problem specification. The problem is
    well defined. It just is not Turing-solvable.

    01 int D(ptr x) // ptr is pointer to int function
    02 {
    03 int Halt_Status = H(x, x);
    04 if (Halt_Status)
    05 HERE: goto HERE;
    06 return Halt_Status;
    07 }

    The input to H(D,D) specifies that D calls its own termination
    analyzer as a part of this computation. The prior definition
    of the halting problem allowed people to incorrectly ignore this.

    Somebody may ignore that particular case but the specification of
    the halting problem says unambigously that
    unless (H(D, D) != 1) <-> D(D) halts
    then H is not a halting decider.

    Mikko

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mikko@21:1/5 to olcott on Tue Jan 16 17:34:09 2024
    On 2024-01-14 00:22:10 +0000, olcott said:

    In computability theory, the halting problem is the problem of
    determining, whether an input finite string pair of program/input
    specifies a computation that would reach a final state and terminate normally.

    01 int D(ptr x) // ptr is pointer to int function
    02 {
    03 int Halt_Status = H(x, x);
    04 if (Halt_Status)
    05 HERE: goto HERE;
    06 return Halt_Status;
    07 }

    The input to H(D,D) specifies that D calls its own termination
    analyzer as a part of this computation. The prior definition
    of the halting problem allowed people to incorrectly ignore this.

    That is not an error in the specification.

    Mikko

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mikko@21:1/5 to olcott on Tue Jan 16 17:32:56 2024
    On 2024-01-14 15:45:16 +0000, olcott said:

    All deciders are required to compute the mapping from their inputs
    in this case on the basis of the behavior SPECIFIED by this input.

    Strawman. The halting problem specification require a Turing machine
    but does not require that it be a decider.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mikko@21:1/5 to olcott on Wed Jan 17 12:20:36 2024
    On 2024-01-14 15:31:17 +0000, olcott said:

    Most people here are making the mistake of believing that when
    the simulation of D is aborted then this simulated D halts.

    As far as I have seen, most people don't.
    A more common mistake seems to be that an aborted simulation of D
    means that the simulated D does not halt.

    Mikko

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)