olcott <NoOne@NoWhere.com> writes:
The following simplifies the syntax for the definition of the Linz
Turing machine Ĥ, it is now a single machine
It always was.
with a single start state.
All TM's have a single start state.
A simulating halt decider is embedded at Ĥ.qx.
This is not "clarifying" but restricting. Linz uses Ĥ to refer to any
TM constructed in a certain way.
It has been annotated so that it only shows Ĥ applied to ⟨Ĥ⟩,
converting the variables to constants.
You don't know what at least two of those these words mean. The result
is a sentence that is "not even wrong".
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
if the simulated input to Ĥ.qx ⟨Ĥ⟩ applied to ⟨Ĥ⟩ reaches its final
state. (Halts)
The correct annotation is the one in Linz: "if Ĥ applied to ⟨Ĥ⟩ halts".
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
if the simulated input to Ĥ.qx ⟨Ĥ⟩ applied to ⟨Ĥ⟩ never reaches its
final state. (Does not halt)
The correct annotation is the one in Linz: "if Ĥ applied to ⟨Ĥ⟩ does not
halt".
You must deny what Linz says because you are not talking about halt
deciders. You are trying to pretend that Linz was talking about
deciders for your other problem:
This definition of halting circumvents the pathological self-reference
error for every simulating halt decider:
An input is decided to be halting only if ...
On that basis:
Ĥ(<Ĥ>) ⊢* Ĥ.qn
H(<Ĥ>,<Ĥ>) ⊢* H.qn
You don't get to say what halting is. It is already well-defined. Any definition that provides a basis for H rejecting a computation that is
finite is garbage.
On 2021-09-30 16:12, olcott wrote:
Because of a critique of my work in another forum I have discovered
that the halt status that H1(P,P) reports is consistent with the
behavior of int main() { P(P); }
But how does this address the Linz proof then? You've derived your P
from H, not from H1. So all that matter with respect to the Linz proof
is what *H*(P, P) returns. That some other decider H1, from which P is
*not* derived, can correctly decide P(P) has no bearing on Linz's claim.
H1 cannot decide P1(P1) where P1 is derived from H1 in the same way that
P is derived from H.
And your proposed 'best of three' test won't work either, since it will
be possible to derive a BestOfThree_Hat construction from your
BestOfThree routine which your BestOfThree routine won't be able to decide.
You don't seem to grasp that Linz is *not* claiming that there are computations whose halting status cannot be decided.
He is claiming that
there cannot be a *universal* halt decider because for every purported
halt decider one can construct a TM which that specific halt decider
cannot correctly decide.
André
On 2021-09-30 18:54, olcott wrote:
On 9/30/2021 7:39 PM, André G. Isaak wrote:
On 2021-09-30 18:26, olcott wrote:
On 9/30/2021 7:18 PM, André G. Isaak wrote:
On 2021-09-30 17:21, olcott wrote:
On 9/30/2021 5:55 PM, André G. Isaak wrote:
On 2021-09-30 16:12, olcott wrote:
Because of a critique of my work in another forum I have
discovered that the halt status that H1(P,P) reports is
consistent with the behavior of int main() { P(P); }
But how does this address the Linz proof then? You've derived
your P from H, not from H1. So all that matter with respect to
the Linz proof is what *H*(P, P) returns. That some other decider >>>>>>> H1, from which P is *not* derived, can correctly decide P(P) has >>>>>>> no bearing on Linz's claim. H1 cannot decide P1(P1) where P1 is
derived from H1 in the same way that P is derived from H.
H(P,P) is correct and H1(P,P) is correct.
So you're saying they both return true? If so, why on earth do you
*need* H1? Why bring it up at all?
H(P,P) correctly determines that its input never reaches its final
state whether or not H aborts the simulation of this input.
H1(P,P) correctly determines that its input reaches its final state.
They have the *same* input. Therefore they cannot both be correct
unless they give the same answer. You can't have one of them claim
that P(P) never reaches its final state and the other say that P(P)
does reach its final state *and* claim they are both correct.
That's Trump Logic.
André
You have to wait until finish converting functions H1 and H to pure
functions. They do derive this result now yet it is possible that this
result is an artifact of their requirement of static local data to
derive these results.
If it works out like preliminary analysis indicates a pair of
functions with identical machine code and identical inputs really do
have different output because the input to H(P,P) calls H and the
input to H1(P,P) calls H (thus does not call H1).
Your statement is entirely incoherent. If H(P, P) and H1(P, P) give
different results then either:
(A) one is wrong.
or
(B) they are not computing the same function, in which case at most
*one* of them can actually be deciding the halting function.
You understand that the halting function (which maps computations to
halting values) is a mathematical object which exists independently of
any Turing Machine or algorithm and has a fixed mapping from
computations to {true, false}, right?
André
On 01/10/2021 01:54, olcott wrote:
On 9/30/2021 7:39 PM, André G. Isaak wrote:
On 2021-09-30 18:26, olcott wrote:
On 9/30/2021 7:18 PM, André G. Isaak wrote:
On 2021-09-30 17:21, olcott wrote:
On 9/30/2021 5:55 PM, André G. Isaak wrote:
On 2021-09-30 16:12, olcott wrote:
Because of a critique of my work in another forum I have
discovered that the halt status that H1(P,P) reports is
consistent with the behavior of int main() { P(P); }
But how does this address the Linz proof then? You've derived
your P from H, not from H1. So all that matter with respect to
the Linz proof is what *H*(P, P) returns. That some other decider >>>>>>> H1, from which P is *not* derived, can correctly decide P(P) has >>>>>>> no bearing on Linz's claim. H1 cannot decide P1(P1) where P1 is
derived from H1 in the same way that P is derived from H.
H(P,P) is correct and H1(P,P) is correct.
So you're saying they both return true? If so, why on earth do you
*need* H1? Why bring it up at all?
H(P,P) correctly determines that its input never reaches its final
state whether or not H aborts the simulation of this input.
H1(P,P) correctly determines that its input reaches its final state.
They have the *same* input. Therefore they cannot both be correct
unless they give the same answer. You can't have one of them claim
that P(P) never reaches its final state and the other say that P(P)
does reach its final state *and* claim they are both correct.
That's Trump Logic.
André
You have to wait until finish converting functions H1 and H to pure
functions. They do derive this result now yet it is possible that this
result is an artifact of their requirement of static local data to
derive these results.
Or some other form of cheating such as a function taking its own
address, and varying its processing according to that address.
(I suggested this was all that was going on a couple of weeks ago, but
you neither confirmed nor denied that. Almost as though you actually
don't understand /yourself/ what's going on. (Surely that cannot be...!))
If it works out like preliminary analysis indicates a pair of
functions with identical machine code and identical inputs really do
have different output because the input to H(P,P) calls H and the
input to H1(P,P) calls H (thus does not call H1).
Of course an /unrestricted/ x86 program can do that - all it has to do
is look at its own address and behave differently according to that
address. (Like your H/H1 routines.) Or cheat with global variables etc..
If you are concerned with saying things of relevance to TMs and Linz's
proof, you need to limit your C code to doing things that directly
correspond with what TMs can do.
Otherwise the relationship between
your computing model and TMs will become distorted and the conclusions
you want to draw from your program's behaviour to TM behaviour may
simply not apply.
I know that last paragraph is WAAAAAY over your head (computation
models? too abstract!) so you will just ignore it. Or perhaps spray
your "Objection Begone!" Turing-equivalence spray at it, which never
works for you. :)
Anyway, you need to work out /why/ copying an algorithm can produce
different behaviour in the copy, and STOP DOING IT!! (Just like you
seem to have recognised that non-pure functions are to be avoided. I'm
not sure whether using your own machine code address breaks the "pure function" rules per se, but the effect on your efforts is the same so it doesn't really matter.)
Mike.
I don't reply to nonsense.
On 10/1/2021 10:27 AM, Andy Walker wrote:
On 01/10/2021 15:12, Mike Terry wrote [to PO, of course]:I think what people are trying to say and may be saying badly is that
Of course an /unrestricted/ x86 program can do that [...]
If you are concerned with saying things of relevance to TMs and
Linz's proof, you need to limit your C code to doing things that
directly correspond with what TMs can do. [...]
     I think it is misleading to talk about what TMs can do as
thought they are interestingly different from what x86 programs or
any real computer can do. An x86 computer /is/ a FSM with extra
storage; in other words, a TM. We tend to write rather simple
TMs to illustrate points, but there is no reason why it should
not have 2^N states, where N is rather large [the number of bits
in your computer]. "Taking the address of a function" is not
"difficult" with a TM, just rather tedious.
     There is no reason why someone [I'm not volunteering!]
should not write a C compiler the target of which is recognisably
a TM. It's just going to be rather complicated. [Probably easier,
AAMOF, to write a microcode as a TM, and describe real computers
in terms of that microcode. In the 1930s, that would have seemed
like magic, but it is how many/most modern computers work.]
     That's why I think people are barking up the wrong tree
when complaining that PO writes C code that is "not a function".
It doesn't matter. It just means that the "hat" construction
is more complicated than PO claims, inc all the states [etc] of
the FSM, inc "hidden" variables. The real errors lie elsewhere.
the set of things that can influence an execution must all be considered
part of that execution. Trivial but important. Said another way apropos
to the current conversation is that when you propose something to play
the role of the Linz H, the definition of that something must include everything that influences its execution. PO doesn't do that. 'It' also
keeps the piece he calls H from being function- or computation-like. One
of the "rules" of software reasoning is that one must carefully delimit
the boundaries of what one is talking about. This basic guideline has
been ignored into oblivion.
On 01/10/2021 17:55, Jeff Barnett wrote:
[I wrote:]
     That's why I think people are barking up the wrong treeI think what people are trying to say and may be saying badly is that
when complaining that PO writes C code that is "not a function".
It doesn't matter. It just means that the "hat" construction
is more complicated than PO claims, inc all the states [etc] of
the FSM, inc "hidden" variables. The real errors lie elsewhere.
the set of things that can influence an execution must all be
considered part of that execution. Trivial but important. [...]
    Absolutely. IOW, the "hat" construction is still possible,
but is not the simplistic version that PO presents.
    [FTAOD, although I was replying to one of your posts, my
article wasn't "aimed" at you, but at the whole way this "debate"
has been going. It's too easy to get sucked in to PO's way of
"thinking".]
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 286 |
Nodes: | 16 (2 / 14) |
Uptime: | 90:30:50 |
Calls: | 6,496 |
Calls today: | 7 |
Files: | 12,100 |
Messages: | 5,277,565 |