The essence of my rebuttal of the Halting Theorem

[olcott]

A simulating halt decider (SHD) correctly predicts what the behavior of
its input would be if it never aborted the simulation of this input. It
does this by correctly recognizing several non-halting behavior patterns
in a finite number of steps of correct simulation. Inputs that do
terminate are simply simulated until they complete.

01 int D(int (*x)())
02 {
03 int Halt_Status = H(x, x);
04 if (Halt_Status)
05 HERE: goto HERE;
06 return Halt_Status;
07 }
08
09 void main()
10 {
11 H(D,D);
12 }

*Here is the sequence when H never aborts it simulation*
main() calls H(D,D) that simulates D(D) at line 11
keeps repeating: simulated D(D) calls simulated H(D,D) that simulates
D(D) at line 03 ...

computation that halts… “the Turing machine will halt whenever it enters
a final state” (Linz:1990:234)

*Anyone competent with software engineering can see*
Every element of the infinite set of H/D pairs where D is correctly
simulated H never (reaches its own final state at line 6) and halts.
Thus H(D,D)==0 is necessarily correct and impossibly incorrect for every
H/D pair that can possibly exist.

When H(D,D) returns 0 it is merely affirming the verified fact that D
correctly simulated by H cannot possibly reach its own last instruction
(final state) at line 6 and halt.

When it is understood that halting requires reaching a final state and
stopping for any other reason does not count as halting then

The fact that D correctly simulated by H cannot possibly reach its own
final state at line 6 conclusively proves that this simulated D does not
halt.

When H aborts its simulation and returns 0 it is only affirming this
verified fact.
The notion of a UTM conclusively proves that D correctly simulated by H
does derive the behavior that a simulating halt decider must measure.

Because all deciders must compute the mapping from their inputs to their
own accept or reject state this mandates that H can only report on D
correctly simulated by H and forbids H from reporting on the behavior of
non-inputs such as D(D).

Anyone and anything that says that H must report on the behavior of
non-inputs contradicts the definition of a decider.

Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company.

--
Copyright 2023 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer

[olcott]

[Ross Finlayson]

The Halting Problem or Entscheidungs the branching problem or
Church-Rice theorem basically establishes that there's arbitrarily
large programs and that for a given static analyzer with given resources
there's exists a sufficiently larger or unbounded program it doesn't have
the resources to analyze, resulting it would either be indeterminate, i.e.,
halting itself, or simply require the resources of the larger program.

But, such terms are in for example about Chaitin's analysis of programs,
about where there are large programs whether Chaitin's number,
reflects processes that may follow branches, where, Chaitin thinks it's
around 85, percent, but, it's as well possible to read it off as 50 percent,
or about the likelihood of following out a program, when such analyses
as are the probabilistic are often done in the Bayesian about the Central
Limit Theorem with the Gaussian or normal or bell distribution about where
50 is just about the mean while 85% is just about one standard deviation,
that of course that's a numerical coincidence.

Any protocol is ultimately cooperative, with the idea for example of balky
protocols that only work with some proof of cooperative work, or something
along the lines of a double-blind. That is to say, it takes a lot of work to
exploit the cooperative aspects of a protocol based on common knowledge,
that has reasonable checks on bounds and resources, whether or not a protocol
is designed to provide contradictions or not.

No static analyzer just runs the program to see whether it halts, though,
if it can be given its own tape then it can be run up until it times out.

Any program though with branching and "flow-of-control" and with
deterministic operations has a static analysis that results those are broken out.

If you provide a program and an input and claim it's undecideable whether
or not it halts, given that it's deterministic the operations about the tape,
I would disagree and suggest that you can not provide a program and an input
thus that it's undecideable whether it halts exits, or enters a circuit and
"loopingly halts", that is instead is decideable, then about various conjectures
of Ackermann numbers or rather about what happens in conjectures in number
theory, where it's decideable or not that generators go to large finite numbers or
not. Then, furthermore "that the large finite numbers have to keep growing, or
not", again provides a breakdown that that's decideable the halting problem for it.


So, I'd suggest that Church-Rice theorem is not so for a given deterministic program
and a given input, that for indeterministic programs or unbounded inputs it's moot.

I suppose it's important for machines who rely on it for their belief systems of tractable
problems that do or don't reduce to number theory reading out whether a generator
after input has finitely or infinitely many elements in finite time, or not, whether then
there's a general program to determine this from number theory's library, then.


I looked at this before because some people just write it out as a corrolary of uncountability
of the reals, then various naive presentations of that were put down.


About the normal forms after lambda calculus, is that interpreting a normal form is a
sort of protocol, so, what could be a small normal form in one protocol is arbitrarily
large in another protocol. Consider for example AND or NOR trees, it's usually considered
things like SAT or satisfiability where it can be written in normal forms, here about normal
forms of the lambda-calculus or Church's recursive. Then, it's one thing to construct a normal
form from a concise form, and, it's another thing to maintain changes in the normal form
that is derived from corresponding forms in the concise, or source. I.e., whether or not
changing the source means rebuilding the entire data structure, gets into why data structures
variously are adaptive, and there's a perfect or optimal data structure for known distributions
of data, then that general data structures may or may not simply be about "usual adaptive data
structures with few usual distributions generally". So anyways, there's some concise forms of
data structure that make things like evaluation of a rules engine, the generator of the lambda,
to have constant-time modifications of the source, linear-time generation of the lambda, then
linear in the size of the source the cost of the lambda. This for example is the yes/no/maybe
or sure/no/yes of a given predicate in any given boolean and binary match predicates, what
results for a row of data a predicate or lambda that can then run in massively parallel the predicate
on the data set, as just a usual kind of example of a reasonably adaptive adaptive algorithm for a
reasonably general data structure that makes modifications cost only constant time instead of
that modifications basically result growing time.

So, that is just getting into that "a normal form" might better be not a "mono-form", that some
"multi-form", is just enough branches to balance adaptivity with expediency and just enough
operations in the resulting abstract machine implementation to differentiate it from a programmable
gate array, as examples of things that Church-Rice would say "don't bother" while fly right off.

[Ross Finlayson]

If it's the same Peter Linz I kind of ignore him since he mis-wrote "time" some years ago.

[olcott]

*This is the fully operational code*
https://github.com/plolcott/x86utm

Where H(D,D) correctly determines the halt status of its input

[Richard Damon]

On 3/22/23 12:02 AM, olcott wrote:
> A simulating halt decider (SHD) correctly predicts what the behavior of
> its input would be if it never aborted the simulation of this input. It
> does this by correctly recognizing several non-halting behavior patterns
> in a finite number of steps of correct simulation. Inputs that do
> terminate are simply simulated until they complete.

Then your "Simulating Halt Deciders" are NOT "Halt Deciders", since Halt
Deciders determine if the machine applied to the input descirbed as the
input to it will halt.

Since D(D) does Halt if H(D,D) returns 0, that can NOT be the correct
answer to a Halt Decider. Halt Deciders need to decide on the actual
machine given to them.

>
> 01 int D(int (*x)())
> 02 {
> 03  int Halt_Status = H(x, x);
> 04  if (Halt_Status)
> 05    HERE: goto HERE;
> 06  return Halt_Status;
> 07 }
> 08
> 09 void main()
> 10 {
> 11  H(D,D);
> 12 }
>
> *Here is the sequence when H never aborts it simulation*
> main() calls H(D,D) that simulates D(D) at line 11
> keeps repeating: simulated D(D) calls simulated H(D,D) that simulates
> D(D) at line 03 ...

But that doesn't matter, since H WILL abort its simulation.

You are just proving that your definition doesn't work on reality but in
a fantasy world.

>
> computation that halts… “the Turing machine will halt whenever it enters
> a final state” (Linz:1990:234)

Right **THE TURING MACHINE**, which means the machine in question, which
in this case is the D that calls actual H that gives the supposeded
correct answer, which is the H that Halts.

You logic above is for a DIFFERENT machine, a D* based on an H* that is
H modified to not halt. Yes D*(D*) doesn't Halt (but H* never gives that
answer) so H(D*,D*) would be correct to return Non-Halting, but it
wasn't given D*, it was given D

>
> *Anyone competent with software engineering can see*
> Every element of the infinite set of H/D pairs where D is correctly
> simulated H never (reaches its own final state at line 6) and halts.
> Thus H(D,D)==0 is necessarily correct and impossibly incorrect for every
> H/D pair that can possibly exist.

Right and every element in that set of pair where H does correctly
simulate D, has an H that never halts to give an answer.

Note, in that set, you let D vary, but D is a FIXED input in the
problem, it calls the H that is claimed to give the right answer.

Your D isn't the D of the actual proof. Your "conversion" to set
notation, rather than giving you cause to claim a correct answer,
actually just proves that NO H by your design ever gave the right
answer, as the only Hs in your set that made non-halting inputs, never
gave an answer, and no H that gave an answer was actually given one of
those Ds as its input.

>
> When H(D,D) returns 0 it is merely affirming the verified fact that D
> correctly simulated by H cannot possibly reach its own last instruction
> (final state) at line 6 and halt.

So, your system allows deciders to answer not on the input given, but
some "similar" machine based on a case that actually isn't.

It still is a fact that for any of the Hn that do this correct
simulation, while they won't answer for the Dn built on them, WILL
correctly answer for the D built on the H that does abort and return 0.

>
> When it is understood that halting requires reaching a final state and
> stopping for any other reason does not count as halting then

Right, and no machine halts for any other reason, as Turing Machine WILL
RUN to completion, as does a "Correct Simulation" by a UTM.

A machine that does a partial simulation and aborts it before reaching a
final state as no data from the fact that it didn't reach a final state
to know if the input halts or not.

That would be like driving a mile on a road and then getting off, and
then being able to tell from just that drive how long the road was.

>
> The fact that D correctly simulated by H cannot possibly reach its own
> final state at line 6 conclusively proves that this simulated D does not
> halt.

But only for D that ARE correctly (and completely) simulated by their H.
Since the actual H doesn't do that, you have no grounds for your claim.

>
> When H aborts its simulation and returns 0 it is only affirming this
> verified fact.

No, it is proving that it wasn't in the set that proved that D was
non-halting.

>
> The notion of a UTM conclusively proves that D correctly simulated by H
> does derive the behavior that a simulating halt decider must measure.

The notion of a UTM means that the only simulation that "matters" for
Halting is one that doesn't abort. Thus no H that abort can be
considered a UTM and thus can't be used as a simulator for determining
Halting.

The notion of a UTM says that a proper Halt Decider could be based on
the definition:

A simulating halt decider (SHD) correctly predicts what the behavior of

its input would be if simulated by a UTM. It does this by correctly

recognizing several non-halting behavior patterns in a finite number of
steps of correct simulation. Inputs that do terminate are simply
simulated until they complete.

THAT works, and UTM(D,D) Halts, so H needs to return Halting.

The problem is your H uses incorrect patterns that don't determine if a
UTM would halt on the input.

>
> Because all deciders must compute the mapping from their inputs to their
> own accept or reject state this mandates that H can only report on D
> correctly simulated by H and forbids H from reporting on the behavior of
> non-inputs such as D(D).
>

It is only ABLE to answer based on what it can compute. It MUST return
the correct answer.

You aren't allowed to change the mapping to be computable and say you
are answering the same question.

THat would be like trying to redefine P to be 3, and saying the
circumference of the unit circle is exactly 6.

> Anyone and anything that says that H must report on the behavior of non-
> inputs contradicts the definition of a decider.

Right, it must report on the ACTUAL behavior of its ACTUAL input, which
is Halting. YOUR H reports on an input that it wasn't given, a D that
calls H* instead of H, the version of H that doesn't abort.