On 2021-11-20 18:35, olcott wrote:
On 11/20/2021 7:12 PM, André G. Isaak wrote:
On 2021-11-20 18:00, olcott wrote:
How do you tell H that it is not allowed to determine the halt
status of its input on the basis of the actual behavior of this
actual input?
The 'input' is a description of an independent computation.
descriptions don't *have* behaviour. It is required to base its
decision on the actual behaviour of the independent computation
described by its input.
This is really not that difficult.
Inputs specify sequences of configurations.
The input to a halt decider is a description of a computation, i.e. a description of a TM and an input string. If you want to call that a
'sequence of configurations', fine, but what's wrong with the standard terminology?
To put this bluntly: Every single computer scientist on earth agrees
on the definition of 'halt decider'. So does virtually every
competent undergraduate who has taken a course on computation. That's
because the definition is precisely defined with absolutely no
ambiguity regarding how it is to be interpreted.
To meet that definition, your H(P, P) *must* report on whether P(P)
halts when called directly from main.
Define the domain of the mathematical function H that says that.
The domain of H is the set of pairs consisting of the description of a
TM and an input string. I already answered that in another post.
A TM *by definition* is an independent, self-contained entity, so there
is no need to specify this. Translating that to C, it means an
independent program (or the sole call inside main), not a function
called from within some other program.
The fact that you don't grasp this just reinforces the fact that you
have no idea what a computation is.
André
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.
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.
Mathematical function H
H maps elements of its domain that specify sequences of configurations
to {0,1} on the basis of whether or not this element reaches its final
state.
The elements of the domain of H are computations. P(P) is a computation.
It halts. Therefore it maps to 1.
This same thing applies to pure function int H(ptr x, ptr y)
it maps sequences of configurations specified by (x, y) to {0,1}.
I already pointed this out in another post (which you ignored) but you
seem to be confused about what 'domain' means (assuming I am
understanding what it is that you are attempting to convey here).
The fact that P(P) is outside the scope of H does not imply that it is outside the domain of H. Scope and domain are different things.
André
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
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'
YOU REALLY NEED TO PAY CLOSER ATTENTION TO THESE DETAILS.
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.
https://cs.stackexchange.com/questions/84433/what-is-decider
TM H
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.
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 Ĥ.
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 ⟨Ĥ⟩ ⟨Ĥ⟩.
But since I am talking about H, this is all irrelevant.
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.
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.
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.
André
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 379 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 66:55:54 |
| Calls: | 8,084 |
| Calls today: | 2 |
| Files: | 13,068 |
| Messages: | 5,849,427 |