On 6/6/2022 12:50 PM, Mr Flibble wrote:
> On Mon, 6 Jun 2022 11:57:57 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 6/6/2022 11:45 AM, Mr Flibble wrote:
>>> On Sun, 5 Jun 2022 20:13:01 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 6/5/2022 7:56 PM, Richard Damon wrote:
>>>>> On 6/5/22 8:27 PM, olcott wrote:
>>>>>> On 6/5/2022 6:59 PM, Mike Terry wrote:
>>>>>>> On 05/06/2022 22:59, Jeff Barnett wrote:
>>>>>>>> On 6/5/2022 2:07 PM, Mike Terry wrote:
>>>>>>>>> On 05/06/2022 16:16, Alan Mackenzie wrote:
>>>>>>>>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com>
>>>>>>>>>> wrote:
>>>>>>>>>>> On 05/06/2022 13:14, Alan Mackenzie wrote:
>>>>>>>>>>>> olcott <NoOne@nowhere.com> wrote:
>>>>>>>>>>>>> On 6/5/2022 6:12 AM, Alan Mackenzie wrote:
>>>>>>>>>>>>>> olcott <NoOne@nowhere.com> wrote:
>>>>>>>>>>>>>>> On 6/5/2022 5:14 AM, Mikko wrote:
>>>>>>>>>>>>>>>> On 2022-06-04 19:28:19 +0000, olcott said:
>>>>>>>>>>
>>>>>>>>>>>>>>>>> A Turing machine is said to halt whenever it reaches a
>>>>>>>>>>>>>>>>> configuration for which δ is not defined; this is
>>>>>>>>>>>>>>>>> possible because
>>>>>>>>>>>>>>>>> δ is a partial function. In fact, we will assume that
>>>>>>>>>>>>>>>>> no transitions are defined for any final state so the
>>>>>>>>>>>>>>>>> Turing machine
>>>>>>>>>>>>>>>>> will halt whenever it enters a final state.
>>>>>>>>>>>>>>>>> (Linz:1990:234)
>>>>>>>>>>
>>>>>>>>>>>>>>>>> Linz, Peter 1990. An Introduction to Formal Languages
>>>>>>>>>>>>>>>>> and Automata.
>>>>>>>>>>>>>>>>> Lexington/Toronto: D. C. Heath and Company.
>>>>>>>>>>
>>>>>>>>>>>>>>>>> When translated into ordinary software engineering
>>>>>>>>>>>>>>>>> terms this means
>>>>>>>>>>>>>>>>> terminated normally. In a C function this means
>>>>>>>>>>>>>>>>> reaching the "ret"
>>>>>>>>>>>>>>>>> instruction.
>>>>>>>>>>
>>>>>>>>>>>>>>>> The best equivalent to "not defined" is not "ret".
>>>>>>>>>>>>>>>> Instead, "not
>>>>>>>>>>>>>>>> defined" should include at least:
>>>>>>>>>>>>>>>> - HLT or any other instruction that means 'halt'
>>>>>>>>>>>>>>>> - any undefined op code
>>>>>>>>>>>>>>>> - any return or pop instruction if the stack is empty
>>>>>>>>>>>>>>>> - an instruction fetch from a location that is not
>>>>>>>>>>>>>>>> specifiec by the
>>>>>>>>>>>>>>>>      program
>>>>>>>>>>>>>>>> That way the analogy to Linz' definition is much
>>>>>>>>>>>>>>>> better.
>>>>>>>>>>
>>>>>>>>>>>>>>>> Mikko
>>>>>>>>>>
>>>>>>>>>>>>>>> Reaching a final state is merely the Turing machine way
>>>>>>>>>>>>>>> of saying
>>>>>>>>>>>>>>> terminated normally. "ret" is the C way of saying the
>>>>>>>>>>>>>>> same thing.
>>>>>>>>>>
>>>>>>>>>>>>>> Sophistry.  What would be the turing machine equivalent
>>>>>>>>>>>>>> of an "abnormal termination" in C?
>>>>>>>>>>
>>>>>>>>>>>>> An aborted simulation.
>>>>>>>>>>
>>>>>>>>>>>> There's no such thing on a turing machine.  It either runs
>>>>>>>>>>>> and halts,
>>>>>>>>>>>> or it runs forever.
>>>>>>>>>>
>>>>>>>>>>>> Your aborted simulation is just one final state of a turing
>>>>>>>>>>>> machine,
>>>>>>>>>>>> which has thus halted.
>>>>>>>>>>
>>>>>>>>>>> A TM "aborting" a simulation is just the TM ceasing to
>>>>>>>>>>> calculate computation steps for some computation, and going
>>>>>>>>>>> on to calculate something else instead.  It does not mean:
>>>>>>>>>>> a)  that the TM (doing the simulation) has halted
>>>>>>>>>>> b)  that the simulated computation halts
>>>>>>>>>>> c)  that the simulated computation never halts
>>>>>>>>>>
>>>>>>>>>> OK.  I've a feeling we're talking more about nice shades of
>>>>>>>>>> words than
>>>>>>>>>> computer science here, but ....
>>>>>>>>>>
>>>>>>>>>> If the simulation is the entire turing machine, aborting it
>>>>>>>>>> will bring
>>>>>>>>>> the TM to a halt state.  If that simulation is merely part of
>>>>>>>>>> the TM, then the word "halt" has a different meaning when
>>>>>>>>>> applied to that simulation part from when applied to the
>>>>>>>>>> entire TM.  I'm not even sure
>>>>>>>>>> what you mean when you say a part of a TM has halted or not
>>>>>>>>>> halted.
>>>>>>>>>
>>>>>>>>> We are clearly talking at cross purposes - I never talked
>>>>>>>>> about /part/ of a TM halting, and like you, I can't work out
>>>>>>>>> what that would mean!  I used "halt" only with respect to a
>>>>>>>>> computation, meaning that the computation halts [there is an n
>>>>>>>>> such that computation step n is a TM final state].
>>>>>>>>>
>>>>>>>>> Reading what you say very carefully, I think that by your
>>>>>>>>> definition of simulation, the simulating TM must be a "pure"
>>>>>>>>> simulator that does nothing but simulate computation steps
>>>>>>>>> until the simulation halts, at which point the simulating TM
>>>>>>>>> halts (like a UTM).  I get that with that interpretation what
>>>>>>>>> you said:
>>>>>>>>>
>>>>>>>>> <copied from above>
>>>>>>>>>  >>> Your aborted simulation is just one final state of a
>>>>>>>>> turing machine,
>>>>>>>>>  >>> which has thus halted.
>>>>>>>>>
>>>>>>>>>   makes sense and is correct.  I'd just say I don't think
>>>>>>>>> that usage of "simulation" is very useful, and is DEFINITELY
>>>>>>>>> not what PO is talking about (so it would be wrong if applied
>>>>>>>>> PO's posts...)
>>>>>>>>>
>>>>>>>>> My use of "simulation" is broader: it's simply the activity
>>>>>>>>> performed by a TM which consists of calculating computation
>>>>>>>>> steps of some given computation.  As such it's just a part of
>>>>>>>>> the TM logic. A TM's typical use of simulation might be
>>>>>>>>> something like "..the TM simulates the computation for n
>>>>>>>>> steps, and if the simulation halts during those n steps, the
>>>>>>>>> TM [blah blah], /otherwise/ the TM [blah blah blah]...". Just
>>>>>>>>> about every reference in the literature I can recall is
>>>>>>>>> something like that.
>>>>>>>>>
>>>>>>>>> So... to be 100% clear on what I said:
>>>>>>>>>
>>>>>>>>> <copied from above>
>>>>>>>>>  >> A TM "aborting" a simulation is just the TM ceasing to
>>>>>>>>> calculate >> computation steps for some computation, and going
>>>>>>>>> on to calculate >> something else instead.
>>>>>>>>>
>>>>>>>>> E.g. in PO's P, after P aborts its simulation of P(P), the TM
>>>>>>>>> either halts or enters an infinite loop.  (That logic is not
>>>>>>>>> part of the simulation, IMO.)
>>>>>>>>>
>>>>>>>>>  >> It does *NOT* mean:
>>>>>>>>>  >> a)  that the TM (doing the simulation) has halted
>>>>>>>>>
>>>>>>>>> obviously, because now P has gone on to something else...
>>>>>>>>>
>>>>>>>>>  >> b)  that the simulated computation halts
>>>>>>>>>  >> c)  that the simulated computation never halts
>>>>>>>>>
>>>>>>>>> obviously - in general different exacmples of a simulated
>>>>>>>>> computation P(I) might halt or never halt, and this is
>>>>>>>>> unaffected by a simulator's decision to simulate no further
>>>>>>>>> computation steps. [The TM may have spotted some pattern in
>>>>>>>>> the simulated computation which implies P(I) never halts -
>>>>>>>>> that is a separate matter, but for sure the mere act of
>>>>>>>>> "aborting" the simulation doesn't imply P(I) never halts, or
>>>>>>>>> imply that it halts...
>>>>>>>>>
>>>>>>>>> Put yet another way, when a TM stops calculating TM steps (aka
>>>>>>>>> aborts its simulation), NOTHING HALTS: not the simulating TM,
>>>>>>>>> not the simulated computation, and NOT ANY PART OF EITHER OF
>>>>>>>>> THOSE. (Like you say, what would part of a TM halting mean?)
>>>>>>>>
>>>>>>>> I think of a TM and an input string as defining a sequence (an
>>>>>>>> ordered list). The elements of the sequence are pairs of a TM
>>>>>>>> state name and a string representing the "tape" contents when
>>>>>>>> the state was entered. Note that this view has no character of
>>>>>>>> animation in it and makes the definition of the halt predicate
>>>>>>>> (H) trivial:
>>>>>>>>
>>>>>>>> H(TM,STRING) = If length of TM(STRING) is finite then TRUE else
>>>>>>>> FALSE.
>>>>>>>
>>>>>>> Yes, that's equivalent to what I said (or at least meant).  Your
>>>>>>> sequence is my computation steps. Formally, these would be
>>>>>>> defined inductively via the rule to go from step n to step n+1.
>>>>>>> (Not an animation, but the induction gives some /sense/ of
>>>>>>> step-by-step calculation, and a simulator will follow this,
>>>>>>> starting at step 1, then calculate step 2 and so on.  Still, I
>>>>>>> agree the entire sequence [the "computation"] exists as one
>>>>>>> timeless structure.  Too abstract for PO...)
>>>>>>>
>>>>>>
>>>>>> In other words when we make sure to conflate the program under
>>>>>> test with the test program as a single computation then the whole
>>>>>> idea of a halt decider becomes less coherent and
>>>>>>
>>>>>> this can be used as an excuse to pretend that you don't already
>>>>>> know that H(P,P)==0 is correct and the H/P relationship matches
>>>>>> the halting problem counter example template.
>>>>>>
>>>>>> void P(u32 x)
>>>>>> {
>>>>>>    if (H(x, x))
>>>>>>      HERE: goto HERE;
>>>>>>    return;
>>>>>> }
>>>>>>
>>>>>> int main()
>>>>>> {
>>>>>>    Output("Input_Halts = ", H((u32)P, (u32)P));
>>>>>> }
>>>>>>
>>>>>>       For any program H that might determine if programs halt, a
>>>>>> "pathological"
>>>>>>       program P, called with some input, can pass its own source
>>>>>> and its input to
>>>>>>       H and then specifically do the opposite of what H
>>>>>> predicts P will do. No H
>>>>>>       can exist that handles this case.
>>>>>> https://en.wikipedia.org/wiki/Halting_problem
>>>>>>
>>>>>>
>>>>>>>>
>>>>>>>> A simulator animates the production of the sequence and that
>>>>>>>> causes some difficulties in the same way that elaborating an
>>>>>>>> infinite sum or sequence does in math classes. An (ultimate)
>>>>>>>> value only exists if there is some notation of convergence or
>>>>>>>> limit which typically is the case with examples used in a math
>>>>>>>> class. There is no definition of convergence or limit with the
>>>>>>>> sequence defined by TM(STRING); rather, we simply ask about the
>>>>>>>> last pair if the sequence is finite.
>>>>>>>
>>>>>>> Sure.
>>>>>>> The question right now is what you would call a TM which
>>>>>>> evaluates the first 10 steps of a computation, and then does
>>>>>>> something else. What is it doing while evaluating those 10
>>>>>>> steps?
>>>>>>>
>>>>>>> tl;dr : who cares :)
>>>>>>>
>>>>>>> My terminology would be that it's "simulating" the computation
>>>>>>> (just for 10 steps) - then it stops simulating and does
>>>>>>> something else. Obviously I wouldn't describe it as "correctly"
>>>>>>> simulating, because nobody considers incorrect simulations, so
>>>>>>> the word would be redundant!
>>>>>>
>>>>>> It is required because my reviewers are making their best
>>>>>> possible effort to form rebuttals and the most persistent of the
>>>>>> fake rebuttals has been that the simulation is incorrect.  It is
>>>>>> very easy to verify the correct x86 emulation on the basis of
>>>>>> the x86 language.
>>>>>
>>>>> Except that it doesn't. By DEFINITION, a correct simulation needs
>>>>> show the same behavior of the thing it is simulating.
>>>>>
>>>>
>>>> Members of comp.c and comp.c++ this goofy idiot is trying to claim
>>>> that it is utterly impossible to create a C program that examines
>>>> the x86 execution trace derived from simulating the input to
>>>> H0(Infinite_Loop) with an x86 emulator to correctly determine that
>>>> Infinite_Loop() infinitely loops.
>>>>
>>>> void Infinite_Loop()
>>>> {
>>>> HERE: goto HERE;
>>>> }
>>>>
>>>> int main()
>>>> {
>>>> Output("Input_Halts = ", H0(Infinite_Loop));
>>>> }
>>>>
>>>> _Infinite_Loop()
>>>> [00001342](01) 55 push ebp
>>>> [00001343](02) 8bec mov ebp,esp
>>>> [00001345](02) ebfe jmp 00001345
>>>> [00001347](01) 5d pop ebp
>>>> [00001348](01) c3 ret
>>>> Size in bytes:(0007) [00001348]
>>>>
>>>> Begin Local Halt Decider Simulation Execution Trace Stored
>>>> at:212343 [00001342][00212333][00212337] 55 push ebp
>>>> [00001343][00212333][00212337] 8bec mov ebp,esp
>>>> [00001345][00212333][00212337] ebfe jmp 00001345
>>>> [00001345][00212333][00212337] ebfe jmp 00001345
>>>> Local Halt Decider: Infinite Loop Detected Simulation Stopped
>>>
>>> But he isn't doing that; the issue is not the infinite loop but the
>>> logic used to decide to enter the infinite loop. Post *full* traces.
>>>
>>> /Flibble
>>>
>>>
>>
>> In other words you are unable to tell that _Infinite_Loop() contains
>> an infinite loop.
>
> Again that isn't the issue; the issue is the logic used to decide when
> to enter the infinite loop;

In other words when H0(Infinite_Loop) is invoked we have no idea that a
correct x86 emulation of Infinite_Loop would reach the instruction at
machine address [00001345] or not.

It might be the case that a correct x86 emulation of Infinite_Loop might
instead involve emulating an entirely different function that plays
tic-tac-toe?

> that decision is a conflation of the
> decider with that which is being decided, a conflation that doesn't
> exist in the HP proofs you are attempting to refute.
>
> /Flibble
>

--
Copyright 2022 Pete Olcott

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