XPost: comp.theory, comp.lang.c, comp.lang.c++

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.

Thus, since the input to H(P,P) represents the computation P(P) [at
least if H claims to be a Halt Decider], then a correct simulation of
that input needs to behave the same actual machine it represents.

Since P(P) Halts if H(P,P) returns 0, then H(P,P) returning 0 can not be
the correct answer for the behavior of P(P).

 Others have referred to that as an "incorrect simulation" because it
stops calculating computation steps before a final state is reached.
[Or maybe it's "incorrect" because after it aborts the simulation, H

My point exactly.

You might be able to claim a correct partial simulation (excpet you
don't trace nesting right), but the partial d

proceeds to return the wrong result?  ..which is considered part of
the simulation?"  ...  Well, there are loads of ok ways to analyse and
phrase what's going on I guess, as long as we're consistent.

But nobody is going to put in all the work required to achieve a
consensus on this

The foundation is simple software engineering that H(P,P)==0 on the
basis that a complete simulation of the input to H(P,P) by H would never reach the "ret" instruction of P.

The ONLY time that H does a COMPLETE SIMULATION, is if H never aborts
its simulation.

H must be a definite program.

If H IS that program that never aborts, then yes, P(P) is non-halting
and Halts(P,P) == 0 would be correct, but H can NEVER generate that
answer, as that behavior was derived from the assumption that H never
aborts its simulation. Thus any argument that breaks that assumption is UNSOUND.

If H does abort its simulation, then it never did a COMPLETE SIMULATION,
and never will, and thus "the complete simulation by H" is a
non-existant entity, it is the liars paradox. You can't base a proof on
the properties of something that doesn't actually exist.

Any claims that these two possibilities for H can exist at the same time
is just an admission that H is not the required computation, as it
doesn;t always act the same way to the same input.

If you want to claim that it is possible for a computation to act
differently for different instances with the exact same input, then you
really need to PROVE that claim. If you can, that alone would make you
famous, but it seems you don't even know enough about the field to
understand the need to prove that claim, so I really doubt you have a
way to prove it. (Again, the proof that it always acts the same is so foundationally simple, I can't imagine you having a way to actually
disprove it.

here, especially with PO who couldn't understand the distinctions.  ]


Mike.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.theory, comp.lang.c, comp.lang.c++

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.

Others
have referred to that as an "incorrect simulation" because it stops calculating computation steps before a final state is reached.  [Or
maybe it's "incorrect" because after it aborts the simulation, H

My point exactly.

proceeds to return the wrong result?  ..which is considered part of the simulation?"  ...  Well, there are loads of ok ways to analyse and
phrase what's going on I guess, as long as we're consistent.

But nobody
is going to put in all the work required to achieve a consensus on this

The foundation is simple software engineering that H(P,P)==0 on the
basis that a complete simulation of the input to H(P,P) by H would never
reach the "ret" instruction of P.

here, especially with PO who couldn't understand the distinctions.  ]

Mike.

--
Copyright 2022 Pete Olcott

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.theory, comp.lang.c, comp.lang.c++

On Sun, 5 Jun 2022 19:27:39 -0500
olcott <NoOne@NoWhere.com> 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

I asserted that it is erroneous to conflate the decider with that which
is being decided several months ago. No such conflation occurs in the
HP proofs you are attempting to refute; it is your conflation which is erroneous.

/Flibble

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.theory, sci.logic, sci.math

On 6/6/2022 11:49 AM, Mr Flibble wrote:

On Sun, 5 Jun 2022 19:27:39 -0500
olcott <NoOne@NoWhere.com> 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

I asserted that it is erroneous to conflate the decider with that which
is being decided several months ago. No such conflation occurs in the
HP proofs you are attempting to refute; it is your conflation which is erroneous.

/Flibble

Did you notice that I was replying to Mike Terry?

--
Copyright 2022 Pete Olcott

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)