XPost: comp.theory, sci.logic, sci.math
On 5/29/22 3:16 PM, olcott wrote:
On 5/29/2022 12:39 PM, Richard Damon wrote:
On 5/29/22 1:19 PM, olcott wrote:
On 5/29/2022 12:04 PM, Mike Terry wrote:
On 29/05/2022 03:43, olcott wrote:
On 5/28/2022 7:22 PM, Mike Terry wrote:
On 27/05/2022 22:32, Richard Damon wrote:
On 5/27/22 5:21 PM, André G. Isaak wrote:
On 2022-05-27 14:38, olcott wrote:
On 5/27/2022 3:06 PM, André G. Isaak wrote:
On 2022-05-27 13:41, olcott wrote:
On 5/27/2022 2:10 PM, André G. Isaak wrote:
On 2022-05-27 13:01, olcott wrote:
On 5/27/2022 1:57 PM, Richard Damon wrote:
The input to H is NOT a "sequence of configuratios", but >>>>>>>>>>>>>> the representation of an algorithm and its input.
The finite string inputs to a halt decider specify (rather >>>>>>>>>>>>> then merely represent) a sequence of configurations that >>>>>>>>>>>>> may or may not reach their own final state.
I really don't think you have any idea what terms like >>>>>>>>>>>> 'represent', 'specify', or 'sequence of configurations' >>>>>>>>>>>> mean. Richard is perfectly correct. You, as usual, are not. >>>>>>>>>>>>
The distinction that I make between represent and specify is >>>>>>>>>>> that the x86 source-code for P represents P(P) whereas the >>>>>>>>>>> actual correct x86 emulation of the input to H(P,P) specifies >>>>>>>>>>> the actual behavior of this input. This is not the same
behavior as the behavior specified by P(P).
A sequence of configurations means a list of x86 program >>>>>>>>>>> steps executed or emulated in the order that their
source-code specifies.
Likewise with a TM or the UTM simulation of a TM description >>>>>>>>>>> specifies a sequence of state transitions.
And this decidedly is *not* what a halt decider is given as >>>>>>>>>> its input. It is not given a sequence of state transitions. It >>>>>>>>>> is given a representation of a computation.
No it is not and you know that it is not. A halt decider is
given a finite string TM description that specifies a sequence >>>>>>>>> of configurations.
A TM description and a sequence of configurations are entirely >>>>>>>> different things (and the former certainly does not 'specify'
the latter). It's given either one or the other. Make up your mind. >>>>>>>>
André
Well, a TM description, and a description of an input to that TM, >>>>>>> does specify a "sequence of configurations" based on what running >>>>>>> that TM on that input would do.
"Specify" is not the word I'd use. (If I write a shopping list I >>>>>> specify what I'm going to get when I go shopping: one loaf of
bread and 4oz jar of strawberry jam. I don't write various clues >>>>>> which can together be used to generate what I want by applying
some algorithm.)
For your scenario, "determine" seems accurate. But PO also says
that P(P) "specifies non-halting behaviour", and that computation
halts. I think that this use just means "matches PO's abort test". >>>>>>
I never said that: "P(P) specifies non-halting behaviour".
Your term "determine" is better than my term "specify".
The input to H(P,P) determines the sequence of x86 instructions of
the correct x86 emulation of P by H. This sequence never reaches
the "ret" instruction of P.
Obviously H never gets to emulate the final ret of P - because it
aborts the emulation before it gets there. Duh! Not seeing the
final ret /because you gave up and stopped emulating/ does not mean
the computation P(P) never halts, or that "never halts" is "the
correct answer" for H to return for input (P,P). That's some
gibberish idea you've come up with in your confusion.
If UTM emulates the P(P) computation, it will see all the EXACT SAME
config steps that H emulated, except that where H gave up due to
spotting some pattern, UTM carries on and sees the P(P) steps after
H gave up, INCLUDING THE FINAL RET OF P.
The correct x86 emulation of the input to H(P,P) by H never reaches
the "ret" instruction of P in 1 to ∞ emulated steps.
No, H will abort it at whatever number of steps would abort that input.
Remember, H is a FIXED algorithm (or needs to be to be a decider) and
thus has DEFINITE behavior for a given input.
Your arguement isn't about a given H, but confounds the behavior of
different members of a whole class of them,
Yes, that is how categorically exhaustive reasoning** works.
** Reasoning that cannot possibly have any gaps.
But it does have gaps.
The alternative method that you suggest is to test each element of an infinite set one-at-a-time.
What infinite set.
H is supposed to be *A* Halt Decider.
You need to show that *IT* is correct.
each generating a DIFFERENT input, and thus not making an actual
arguement about any of the input.
The literal string of machine code bytes is the only actual input.
WRONG. That string of code does NOT define the behavior of the PROGRAM
P, because it doesn't define the contents of the memory at 000011A2
THAT is the "GAP" in your logic.
_P()
[00001352](01) 55 push ebp
[00001353](02) 8bec mov ebp,esp
[00001355](03) 8b4508 mov eax,[ebp+08]
[00001358](01) 50 push eax // push P [00001359](03) 8b4d08 mov ecx,[ebp+08]
[0000135c](01) 51 push ecx // push P [0000135d](05) e840feffff call 000011a2 // call H [00001362](03) 83c408 add esp,+08
[00001365](02) 85c0 test eax,eax
[00001367](02) 7402 jz 0000136b
[00001369](02) ebfe jmp 00001369
[0000136b](01) 5d pop ebp
[0000136c](01) c3 ret
Size in bytes:(0027) [0000136c]
H is defined to be at machine address 000011a2.
WHICH H? You said H is an infinite set of deciders. You have just
defined that No H can actually look at a P that does't use it.
Let us lable each of the members of that set H as Hi where i is the
number of steps that it will simulate its corresponding Pi before
aborting it.
First thing to note, as defined, your H's fail to be valid halt deciders
as it is impossible to give Hi the input Pj,Pj for j != i, so there are
inputs it BY YOUR DEFINITION can't answer. Let us fix that by making an
actual copy of the code of H (as Linz says to do) and include that in P,
and make that call go to that one, thus for the code above 000011a2 has
diffent contents for the different Pi's based on the value of i and will
always be the corresponding Hi.
If you can't even give your decider all computations, it just fails to
meet the definition.
Now, when we look at the set of exprements you run, you show that for
every Hi, when called as Hi(Pi,Pi) that by the i'th step it hasn't
reached the return statement. That means you have shown that for all i,
Pi doesn't halt in i steps.
If all the Pi's were the same (call it Q), then you could argue that you
have shown that for any finite number i, Q doesn't halt in that time,
and thus Q doesn't halt.
But, since the Pi's differ, that induction doesn't work, all you have
proven is that for i = infinity that Pi doesn't halt, i.e, the Pi built
on an H that simulates forever doesn't halt.
In the past, we have labeled that H, the one that never aborts, as Hn
(for H non-aborting), and yes, you have just proved that Pn(Pn) is a non-halting computation, but unfortunately, it is also shown that
Hn(Pn,Pn) never aborts its simulation to give that answer.
And also, it has been shown that for any finite i, that while Hi(Pi,Pi)
never reaches the halt instruction in its simulation, there is a k (a
function of i and >i) such that all Hk(Pi,Pi) will simulate its input to
the ret instruction, and thus show that Hi aborted its simulation too soon.
If you are going to argue over all H, you need to FULLY argue over all
H, and that means that 'Correct Simulation' means by ANY H, thus that
fact that Hk can simulate to the ret, means Hi was WRONG to abort its simulation.
This is the fallacy of your notation. Your H keeps on being shown to
not be a definite algorithm, so it can't be a Halt Decider.
There are only two possible ways that H can be defined:
(a) H that aborts its simulation after some fixed number of emulated steps.
And thus its simulation is NOT actually a "Correct Simulation" by the definition needed to use "Correct Simulation" as a critera for Halting.
Once you change your definition to allow partial simulations to be
considered "Correct", you have lost the right to say a "Correct
Simulation" determines halting, but you HAVE to go back to the original behavior of the machine, and it is shown that P(P) Halts if H(P,P)
returns 0, and thus the correct answer to H(P,P) would have been 1
(which it didn't give, and in fact if it did, that would be a DIFFERENT
P, and wrong for that P).
Remember, the DEFINITION of Halting is based on the TURING MACHINE
itself. If you use simulation per the definition of a UTM, (which, by definition matches the machine, and thus never aborts) then you can
substitute that simulation. If your definition of simulation deviates
from that IN ANY WAY, it is invalid to make that transformation.
YOU FAIL.
(b) H that does not abort its simulation after some fixed number of
emulated steps.
And it is shown that this H never answer.
In neither of these categorically exhaustive cases does the correctly emulated input to H(P,P) ever reach its "ret" instruction.
WRONG. For case (a) it is shown that H aborts its simulation too soon.
Only by INVALID logic do you reach your result.
THus, it has been shown that for ANY of the H's so defined, that H does
NOT give the correct answer for the P derived from THAT H, thus that H
fails to be a counter example.
For ANY H built by your rule (a), it is shown that P(P) will Halt when
its H(P,P) returns 0, and thus that 0 is the wrong answer.
For ANY H built by your rule (b), it is shown that that H never answer
H(P,P), and so fails to be a decider.
Only by conflating the P's built by those two different method does your arguement SEEM to make some sense, but is shown to be incorrect.
FAIL.
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)