XPost: comp.theory, sci.logic, sci.math

On 11/13/2021 8:25 AM, Mr Flibble wrote:

Definition of the halting problem (from Wikipedia):

For any program f that might determine if programs halt, a
"pathological" program g, called with some input, can
pass its own source and its input to f and then
specifically do the opposite of what f predicts g will
do. No f can exist that handles this case.

The reason no f can exist for the case described is because it involves
an INVALID infinite recursion and NOT because a general algorithm that
can answer the question as to whether a program and its given input
halts or runs for ever cannot exist.

I brought up the idea that the halting theorem counter-examples specify infinite recursion in this forum Mar 11, 2017, 3:13:03 PM

The problem is that every H-Hat needs a pair of inputs.

H-Hat takes an H-Hat as input and copies it so that it
can analyze how its input H-hat would analyze the copy
of H-Hat that it just made.

The input H-Hat would have to copy its own input H-Hat
so that it can analyze what its own input H-Hat would
do on its own input, on and on forever...

https://groups.google.com/g/comp.theory/c/NcFS02hKs1U/m/PlBF-1LRBAAJ

The key to understanding this is to recognize that the pathological
infinite recursion described above is INVALID for the same reason that
a recursive definition is INVALID; this is NOT the same as

I would not say that it is invalid although that is what I did say in
2004. Sep 5, 2004, 11:21:57 AM comp.theory

The Liar Paradox can be shown to be nothing more than
a incorrectly formed statement because of its pathological
self-reference. The Halting Problem can only exist because
of this same sort of pathological self-reference.

The primary benefit of solving the Halting Problem was to
detect programs that failed to halt, thus were incorrect.
Pathological self-reference can also be viewed as a form
of error.

https://groups.google.com/g/comp.theory/c/RO9Z9eCabeE/m/Ka8-xS2rdEEJ

infinite recursion due to normal recursive function calls defined
within a non-pathological program which can be viewed as:

a) non-halting (infinite stack for recursion)
b) non-halting (tail recursion being optimized into an infinite loop)
c) halting (finite stack exhausted)

/Flibble

My new paper is
(a) much more compelling
(b) much simpler
(c) much shorter
(d) defines both H and P as pure functions thus computable.

Halting problem undecidability and infinitely nested simulation (V2)
November 2021 PL Olcott

https://www.researchgate.net/publication/356105750_Halting_problem_undecidability_and_infinitely_nested_simulation_V2



--
Copyright 2021 Pete Olcott

Talent hits a target no one else can hit;
Genius hits a target no one else can see.
Arthur Schopenhauer

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

XPost: comp.theory, sci.logic, sci.math

On 11/13/2021 8:59 AM, Mr Flibble wrote:

On Sat, 13 Nov 2021 09:54:33 -0500
Richard Damon <Richard@Damon-Family.org> wrote:

On 11/13/21 9:25 AM, Mr Flibble wrote:

Definition of the halting problem (from Wikipedia):

For any program f that might determine if programs halt, a
"pathological" program g, called with some input, can
pass its own source and its input to f and then
specifically do the opposite of what f predicts g will
do. No f can exist that handles this case.

The reason no f can exist for the case described is because it
involves an INVALID infinite recursion and NOT because a general
algorithm that can answer the question as to whether a program and
its given input halts or runs for ever cannot exist.

The key to understanding this is to recognize that the pathological
infinite recursion described above is INVALID for the same reason
that a recursive definition is INVALID; this is NOT the same as
infinite recursion due to normal recursive function calls defined
within a non-pathological program which can be viewed as:

a) non-halting (infinite stack for recursion)
b) non-halting (tail recursion being optimized into an infinite
loop) c) halting (finite stack exhausted)

/Flibble

Incorrect.

Given a claimed Turing Machine H that is supposed to return the
correct halting decision of the computation that is provided as its
input, the formation of the H^ Turing Machine is a simple mechanical
operation, as is converting the machine into a description <H^> to
give to H or H^. Thus there is on INVALID machine creation, given the
assumption that the original H was properly provided.

There is nothing about the problem statement that requires the H to
be infinitely recursive, and there are many examples of partial halt
deciders that are most definitely valid.

There is nothing INVALID in view here, merely that it has been shown
that when we look at the countably infinite number of Turing Machines
possible, that NONE of them have the needed property. It isn't that
there is something that has outlawed that machine, it just doesn't
exist.

You miss the fact that infinite behavior is NOT 'INVALID' for Turing
Machines, we just require that Turing Machines that are classified as
'Deciders' never have that type of behavior.

You are incorrect. The halting problem as currently defined is basically
a category error; recursive definitions are bogus.

/Flibble

You are the only other person that ever noticed this. As it turns out
this recursive definition is simply decidable as never halting.


My new paper is
(a) much more compelling
(b) much simpler
(c) much shorter
(d) defines both H and P as pure functions thus computable.

Halting problem undecidability and infinitely nested simulation (V2)
November 2021 PL Olcott

https://www.researchgate.net/publication/356105750_Halting_problem_undecidability_and_infinitely_nested_simulation_V2


--
Copyright 2021 Pete Olcott

Talent hits a target no one else can hit;
Genius hits a target no one else can see.
Arthur Schopenhauer

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