Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

Packages should build-depend on what they should build-depend. -- Santiago Vila on debian-devel

computers / / Re:_Concise_refutation_of_halting_problem_proofs_V21_[_André_is_wrong_]

Subject: Re:_Concise_refutation_of_halting_problem_proofs_V21_[_André_is_wrong_]
From: olcott
Newsgroups: comp.theory,, sci.logic, sci.math
Followup: comp.theory
Date: Mon, 22 Nov 2021 01:45 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
NNTP-Posting-Date: Sun, 21 Nov 2021 19:45:45 -0600
Date: Sun, 21 Nov 2021 19:45:43 -0600
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Subject: Re:_Concise_refutation_of_halting_problem_proofs_V21_
Content-Language: en-US
Newsgroups: comp.theory,,sci.logic,sci.math
References: <>
<sn9c8i$522$> <>
<sna68l$89c$> <>
<snbk9q$s3k$> <>
<snc4pv$dfv$> <>
<snc5fl$hlj$> <>
<snc6el$nga$> <snc7o6$tme$>
<snc945$49e$> <>
<sncbb8$huh$> <>
<sncg69$8au$> <>
<sndlot$qau$> <>
<sndu4l$lp6$> <>
<sneb1c$gf5$> <>
From: (olcott)
Followup-To: comp.theory
In-Reply-To: <snelu4$srg$>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <>
Lines: 300
X-Trace: sv3-sPQ611sJaGLrcMkuxKVB/6ptx96EdZty4Uu4ULHtJeM2MChGXYAn2liUb4Kg6X+DlX0wbsoV69WlMi+!nisVH640qMQBkn2mW3eVQyIFU94eV1cCKdQWmz0OlgHid9n+vaxoZ4b1h+cPJ4/d6A76AyhD9sXK!tw==
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 14211
View all headers
On 11/21/2021 5:49 PM, André G. Isaak wrote:
On 2021-11-21 14:09, olcott wrote:
On 11/21/2021 2:43 PM, André G. Isaak wrote:
On 2021-11-21 13:13, olcott wrote:
On 11/21/2021 11:03 AM, André G. Isaak wrote:
On 2021-11-21 09:04, olcott wrote:
On 11/21/2021 8:40 AM, André G. Isaak wrote:
On 2021-11-20 21:20, olcott wrote:
On 11/20/2021 9:59 PM, André G. Isaak wrote:
On 2021-11-20 20:16, olcott wrote:
On 11/20/2021 8:36 PM, André G. Isaak wrote:

The "sequence of configurations specified by ⟨Ĥ⟩ ⟨Ĥ⟩" is simply the computation Ĥ(Ĥ). The INDEPENDENT computation Ĥ(Ĥ). And that computation halts.

There is a one way dependency relationship of the behavior of P on the return value of H that cannot simply be assumed away.

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

There is a one way dependency relationship of the behavior of Ĥ on the state transition of Ĥ.qx that cannot simply be assumed away.

No one is assuming anything away. That dependency is precisely *why* H can never give the correct answer, which is the entire point of the Linz proof.

It is a fallacy of equivocation error to assume that this dependency does not cause different behavior between these two different instances.

There is no equivocation here (do you even understand what that word means?)

Yes, in your implementation the two instances act differently. But the halting problem is very clear about *which* instance your decider needs to answer about. It needs to describe the behaviour of P(P), not of the simulation inside your H.

That is not a proper mathematical function.

I don't think you're in a position to determine what is or is not a 'proper' mathematical function.

H maps specified sequences of configurations in its domain to {0,1}

H maps computations to {0, 1} or it is not a halt decider. P(P) is a computation which halts. H therefore maps this to 1.

If H maps sequences of configurations that specify computations then according to the Linz definition of computation

The sequence of configurations leading to a halt state will be called a computation.  (Linz:1990:238)

Every input to H halts thus every H can simply say YES and be correct

If you read the section of Linz on the halting problem you will note that Linz also talks about halting and non-halting computations. While 'computation' is often restricted to algorithms (i.e. things guaranteed to halt) this is not the case when talking about halt deciders.

If it's less confusing for you, simply replace 'computation' with 'TM description + input string'


I have no idea how you are interpreting the expression 'sequence of configurations', but unless it is intended to mean a description of a TM and an input string, you are barking up the wrong tree.

It includes a description of a TM and an input string and several other things such as a pair of machine addresses of x86 code and a pair of finite strings of x86 code.

int H(ptr x, ptr y)
H maps sequences of configurations specified by (x,y) to {0,1}

The same things apply here.

The sequence of configurations specified by (x, y) are the basis of the decision of H to accept or reject these inputs.

All deciders accept or reject inputs, and have no other decision basis.

computer science decider
Intuitively, a decider should be a Turing machine that given an input, halts and either accepts or rejects, relaying its answer in one of many equivalent ways, such as halting at an ACCEPT or REJECT state, or leaving its answer on the output tape.

H maps specified sequences of configurations on its tape to {0,1}

This primary path of rebuttal is now closed:
I have concretely proven that the input to H(P,P) never halts and the exact same P(P) halts for the PSR subset and the Decidable_PSR subset in both cases H is a pure function.

H(P, P) must answer about P(P) because that's what a halt decider does.

No you are wrong.

That's the DEFINITION of what a halt decider does.

That is your misinterpretation
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞

Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ is not being asked about sequences of configurations of its itself or the sequences of configurations of the computation that it is contained in.

Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ is being asked about the sequences of configurations specified on its tape.

The symbols on the tape are a description of the independent computation Ĥ(⟨Ĥ⟩). Why is this so difficult for you to grasp?

This is the crux of the most difficult last step that has prevented everyone in the world from coming to the correct conclusion about the halting theorem.

There is no way to mathematically specify (to the halt decider) the distinction between the behavior of the direct UTM simulation of this input by the halt decider and the independent execution of this same input at some other point in the execution trace outside of the halt decider.

Of course there is a way. The independent execution is specified as ⟨Ĥ⟩ ⟨Ĥ⟩. The simulation by a UTM would be ⟨UTM⟩ ⟨Ĥ⟩ ⟨Ĥ⟩. Those are two distinct computations.

Your H doesn't even involve a UTM, so why you bring this up is beyond me.

What you are failing to grasp is that when you run H ⟨Ĥ⟩ ⟨Ĥ⟩, the *only* computation which is actually occuring is H ⟨Ĥ⟩ ⟨Ĥ⟩. Even if H reaches its decision by partially simulating H ⟨Ĥ⟩, there is no computation H ⟨Ĥ⟩ taking place inside of the decider. The simulation is simply *part* of the steps involved in computing H ⟨Ĥ⟩ ⟨Ĥ⟩ and is not a computation itself, so it isn't even in the domain of the problem.

Or, to put things in terms of your poor analogy below, there only *is* one window to choose from.

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

You already chose the second window.

H ⟨Ĥ⟩ ⟨Ĥ⟩ is one window like P(P)

and Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ is entirely different window like H(P,P)

What are you on about here? I am trying to explain to you what the definition of a *halt* decider is. Ĥ.qx is a single state inside of Ĥ. There is no such state inside H.

Ĥ.qx is not a single state it is the first state of Ĥ where the copy of H begins.

H ⟨M) w evaluates whether M w halts.

If you ask me to look out my window to see if it is raining I can tell you a definite and correct answer.

If you ask me to look out my window to see if it is raining when looking out Ben's window in Florida then the answer based on looking out my window would be incorrect.

And if I give a Halt decider the input string ⟨Ĥ⟩ ⟨Ĥ⟩, that tells it to evaluate the behaviour of computation H ⟨Ĥ⟩.

There are no H's to be found in
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

And so what? I explaining what a halt decider must do. That would be H, not Ĥ.

We must figure out what Ĥ.qx would do and what H would do and it is common sense that they must do the same thing none-the-less they do not do the same thing.

So now you are looking outside of a window that does not exist.

It does not tell it to look evaluate the behaviour of some internal simulation.

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
does tell Ĥ.qx to evaluate the behavior of Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩

Ĥ.qx is simply a single state. It doesn't evaluate anything. And I have no idea what it means for something to evaluate the behaviour of Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩.

Ĥ.qx  IS NOT a single state it is the point in Ĥ where its copy of H begins.

But since I am talking about H, this is all irrelevant.

I am not talking about H. I am talking about the behavior of the copy of H at Ĥ.qx

It can make use of such a simulation as part of its analysis, but unless the answer corresponds to the actual behaviour of H ⟨Ĥ⟩ then its analysuis is wrong.

H ⟨Ĥ⟩ ⟨Ĥ⟩ bases its decision on the actual behavior of Ĥ ⟨Ĥ⟩

Yes, the *actual* behaviour of Ĥ ⟨Ĥ⟩. The actual behaviour of Ĥ ⟨Ĥ⟩ is that it halts.

The copy of H at Ĥ.qx cannot simply wait for itself to decide what itself is going to do. Whereas H can wait so see what ⟨Ĥ⟩ ⟨Ĥ⟩ does.

That your 'simulation' doesn't match the behaviour of this independent computation indicates a problem with your simulator; it doesn't impact the actual meaning of the input string.

That it is not raining outside of my window has zero predictive value for the presence or absence of rain looking out Ben's window.

Similarly, looking at anything other than the behaviour of the independent computation Ĥ ⟨Ĥ⟩ has zero predictive value for determining the halting status of Ĥ ⟨Ĥ⟩. Your decider is looking out the wrong window.

So Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ must base its analysis on what the behavior of its input would be if Ĥ.qx was H, How is Ĥ.qx supposed to know that ?

I cannot for the life of me even figure out what you are trying to claim here.

This can only be properly understood in terms of the four precisely defined sets on half a page of page 3.

The first two sets are easy for any competent software engineer:

The existence of the third set conclusively proves that the input to H(P,P) never halts and P(P) halts for the exact same H and P.

Understanding this is the key to understanding that Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩
correctly decides the halt status of its input.

Halting problem undecidability and infinitely nested simulation (V2)

  There is no way to separately distinguish an independent computation P(P) from a UTM simulation of (P,P) to any math function C function or TM decider therefore the simulation of the input to H must always be a correct basis.

P ⟨P⟩ vs. UTM ⟨P⟩ ⟨P⟩

And those are distinct computations. H ⟨P⟩ ⟨P⟩  must base its decision on P ⟨P⟩

H ⟨UTM⟩ ⟨P⟩ ⟨P⟩ must base its decision on UTM ⟨P⟩ ⟨P⟩.

Both of those halt, so in both cases H must return 1.

Your H returns 0.


Copyright 2021 Pete Olcott

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

o Concise refutation of halting problem proofs V18

By: olcott on Fri, 19 Nov 2021

rocksolid light 0.7.2