On Tuesday, 31 May 2022 at 13:35:24 UTC+1, Malcolm McLean wrote:
On Monday, 30 May 2022 at 15:35:38 UTC+1, olcott wrote:
We can't "assume a simulating halt decider" because the proof shows,
When we assume a simulating halt decider then none of the simulated
inputs to the conventional proofs ever reach their final state when
correctly simulated by this simulating halt decider.
That you don't understand this does not make it false.
or at least claims to show, that a simulating halt decider can't exist.
On 5/31/2022 4:05 PM, Malcolm McLean wrote:
On Tuesday, 31 May 2022 at 13:35:24 UTC+1, Malcolm McLean wrote:
On Monday, 30 May 2022 at 15:35:38 UTC+1, olcott wrote:
We can't "assume a simulating halt decider" because the proof shows,
When we assume a simulating halt decider then none of the simulated
inputs to the conventional proofs ever reach their final state when
correctly simulated by this simulating halt decider.
That you don't understand this does not make it false.
or at least claims to show, that a simulating halt decider can't exist.
None of the proofs bother to specifically examine simulating halt
deciders this is their big mistake. All of the proofs simply assume that
the execution trace of the input to H(P,P) reaches the
self-contradictory part. This is a provably false assumption.
On Wednesday, 1 June 2022 at 20:03:43 UTC+1, Ben wrote:
Malcolm McLean <malcolm.ar...@gmail.com> writes:The "simulating halt decider" will fail when fed H_Hat, not because of the invert
And actually, what you have done is construct a simulating attempted halt >>> decider, which fails on H_Hat, for reasons unrelated to the invertWhat? H_Hat(H_Hat) halts because H(H_Hat, H_Hat) == 0 so, yes, no loop
loop.
is involved, but that's not interesting.
So you have actually achieved something of interest, if you could onlyWhat do you think is new or interesting here? I can't see anything new
recognise that.
or interesting here at all.
step, but because it can't solve the simulation of H. That's inherent in the way
it is set up - it can only terminate if it detects that the series of nested simulations is non-terminating, in which case it becomes terminating.
I don't think anyone has actually pointed that out before. It's not going to revolutionise computer science. But it is an interesting observation.
On 6/2/2022 6:19 AM, Malcolm McLean wrote:
On Wednesday, 1 June 2022 at 20:03:43 UTC+1, Ben wrote:
Malcolm McLean <malcolm.ar...@gmail.com> writes:The "simulating halt decider" will fail when fed H_Hat, not because of
And actually, what you have done is construct a simulating attemptedWhat? H_Hat(H_Hat) halts because H(H_Hat, H_Hat) == 0 so, yes, no loop
halt
decider, which fails on H_Hat, for reasons unrelated to the invert
loop.
is involved, but that's not interesting.
So you have actually achieved something of interest, if you could only >>>> recognise that.What do you think is new or interesting here? I can't see anything new
or interesting here at all.
the invert
step, but because it can't solve the simulation of H. That's inherent
in the way
it is set up - it can only terminate if it detects that the series of
nested
simulations is non-terminating, in which case it becomes terminating.
That is not the point. The simulated input to H(P,P) only halts if it
reaches its "ret" instruction otherwise it is non-halting.
P(P) does halt yet it is an entirely different sequence of x86
instructions than the correctly simulated input to H(P,P).
People here say that they really really don't believe this thus directly disagree with the x86 language. This is a move that only one person here
is dumb enough to make, yet more than one person does.
I don't think anyone has actually pointed that out before. It's not
going to
revolutionise computer science. But it is an interesting observation.
Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
On Wednesday, 1 June 2022 at 20:03:43 UTC+1, Ben wrote:
Malcolm McLean <malcolm.ar...@gmail.com> writes:The "simulating halt decider" will fail when fed H_Hat, not because of
And actually, what you have done is construct a simulating attempted halt >>>> decider, which fails on H_Hat, for reasons unrelated to the invertWhat? H_Hat(H_Hat) halts because H(H_Hat, H_Hat) == 0 so, yes, no loop
loop.
is involved, but that's not interesting.
So you have actually achieved something of interest, if you could only >>>> recognise that.What do you think is new or interesting here? I can't see anything new
or interesting here at all.
the invert step, but because it can't solve the simulation of H.
What's new or interesting about that? A simulating partial halt decider really only has only two ways to be wrong: fail to return a result or incorrectly decide some halting computations as non-halting (ignoring
cases where it's designed to be deliberately wrong unnecessarily).
And H_Hat never has anything to do with why a decider is wrong because
we can show that any purported halt decider must get infinitely many instances wrong, so there will be an abundance of examples that have
nothing to do with H_Hat.
But none of this is what PO is claiming. He claims H is right to be
wrong so you have your work cut out if you want to get him to accept
that H really is wrong, even if you find the reason interesting.
That's inherent in the way
it is set up - it can only terminate if it detects that the series of nested >> simulations is non-terminating, in which case it becomes terminating.
No, it terminates because it /incorrectly/ concludes that the nested simulations are non-terminating. PO's silly argument is that this
conclusion is not wrong because the nested simulations /would/ be non-terminating if they were not terminated. Go figure.
I don't think anyone has actually pointed that out before. It's not going to >> revolutionise computer science. But it is an interesting observation.
Why would anyone want to point this out? We know simulation can't be
used to decide halting, and we know that there are only two ways a
decider that tries to do so can be wrong. Both come up every time this
is taught to a class of programmers. (I've never taught it to a class
of mathematicians but I suspect the discussion would be very different.)
On 02/06/2022 12:19, Malcolm McLean wrote:
On Wednesday, 1 June 2022 at 20:03:43 UTC+1, Ben wrote:
Malcolm McLean <malcolm.ar...@gmail.com> writes:The "simulating halt decider" will fail when fed H_Hat, not because of
And actually, what you have done is construct a simulating attemptedWhat? H_Hat(H_Hat) halts because H(H_Hat, H_Hat) == 0 so, yes, no loop
halt
decider, which fails on H_Hat, for reasons unrelated to the invert
loop.
is involved, but that's not interesting.
So you have actually achieved something of interest, if you could only >>>> recognise that.What do you think is new or interesting here? I can't see anything new
or interesting here at all.
the invert
step, but because it can't solve the simulation of H. That's inherent
in the way
it is set up - it can only terminate if it detects that the series of
nested
simulations is non-terminating, in which case it becomes terminating.
..in which case it becomes terminating BECAUSE OF THE INVERT STEP.
On 02/06/2022 17:21, Ben wrote:
[...] We know simulation can't be
used to decide halting, and we know that there are only two ways a
decider that tries to do so can be wrong. Both come up every time this
is taught to a class of programmers. (I've never taught it to a class
of mathematicians but I suspect the discussion would be very different.)
My first thought was "no, it's the same", but on reflexion, and AFAIR,
our mathematicians simply accepted what I told them, which is
essentially what
is at
http://www.cuboid.me.uk/anw/G12FCO/lect17.html
[second half, but see esp the last paragraph] and
http://www.cuboid.me.uk/anw/G12FCO/lect18.html
[both lectures from a module that I gave many moons ago]. We got pretty bright students, among the top four or five cohorts in the UK at that time [1990s] [but that was our high point, even beating Oxford one year], and of course many of them went into IT as a career. They found NP-completeness much harder than UTMs, HP and related stuff.
[The code G12FCO means G1 -- maths, 2 -- second year, FCO -- Formal Computation.]
Andy Walker <anw@cuboid.co.uk> writes:
On 02/06/2022 17:21, Ben wrote:
[...] We know simulation can't be
used to decide halting, and we know that there are only two ways a
decider that tries to do so can be wrong. Both come up every time this
is taught to a class of programmers. (I've never taught it to a class
of mathematicians but I suspect the discussion would be very different.)
My first thought was "no, it's the same", but on reflexion, and AFAIR, >> our mathematicians simply accepted what I told them, which is essentially what
is at
http://www.cuboid.me.uk/anw/G12FCO/lect17.html
[second half, but see esp the last paragraph] and
http://www.cuboid.me.uk/anw/G12FCO/lect18.html
I see your notes are an explicit counterexample to PO's claims that
emulation is never considered!
[both lectures from a module that I gave many moons ago]. We got pretty
bright students, among the top four or five cohorts in the UK at that time >> [1990s] [but that was our high point, even beating Oxford one year], and of >> course many of them went into IT as a career. They found NP-completeness
much harder than UTMs, HP and related stuff.
We got pretty bright students too. Bright students ask good questions
but eventually (rapidly even) settle the matter to their own
satisfaction.
And I agree that complexity is more... complex. The details become so
very significant in complexity theory. One of the depressing things
about these endless threads is that this is not a complex theorem.
Andy Walker <anw@cuboid.co.uk> writes:
On 02/06/2022 17:21, Ben wrote:
[...] We know simulation can't be
used to decide halting, and we know that there are only two ways a
decider that tries to do so can be wrong. Both come up every time this
is taught to a class of programmers. (I've never taught it to a class
of mathematicians but I suspect the discussion would be very different.)
My first thought was "no, it's the same", but on reflexion, and AFAIR, >> our mathematicians simply accepted what I told them, which is essentially what
is at
http://www.cuboid.me.uk/anw/G12FCO/lect17.html
[second half, but see esp the last paragraph] and
http://www.cuboid.me.uk/anw/G12FCO/lect18.html
I see your notes are an explicit counterexample to PO's claims that
emulation is never considered!
[both lectures from a module that I gave many moons ago]. We got pretty
bright students, among the top four or five cohorts in the UK at that time >> [1990s] [but that was our high point, even beating Oxford one year], and of >> course many of them went into IT as a career. They found NP-completeness
much harder than UTMs, HP and related stuff.
We got pretty bright students too. Bright students ask good questions
but eventually (rapidly even) settle the matter to their own
satisfaction.
And I agree that complexity is more... complex. The details become so
very significant in complexity theory. One of the depressing things
about these endless threads is that this is not a complex theorem.
On 02/06/2022 17:21, Ben wrote:
[...] We know simulation can't be
used to decide halting, and we know that there are only two ways a
decider that tries to do so can be wrong. Both come up every time this
is taught to a class of programmers. (I've never taught it to a class
of mathematicians but I suspect the discussion would be very different.)
My first thought was "no, it's the same", but on reflexion, and AFAIR,
our mathematicians simply accepted what I told them, which is
essentially what
is at
http://www.cuboid.me.uk/anw/G12FCO/lect17.html
[second half, but see esp the last paragraph] and
http://www.cuboid.me.uk/anw/G12FCO/lect18.html
[both lectures from a module that I gave many moons ago]. We got pretty bright students, among the top four or five cohorts in the UK at that time [1990s] [but that was our high point, even beating Oxford one year], and of course many of them went into IT as a career. They found NP-completeness much harder than UTMs, HP and related stuff.
[The code G12FCO means G1 -- maths, 2 -- second year, FCO -- Formal Computation.]
On Thu, 2 Jun 2022 15:47:22 -0500
olcott <NoOne@NoWhere.com> wrote:
On 6/2/2022 1:12 PM, Andy Walker wrote:
On 02/06/2022 17:21, Ben wrote:
[...] We know simulation can't be
used to decide halting, and we know that there are only two ways a
decider that tries to do so can be wrong. Both come up every time
this is taught to a class of programmers. (I've never taught it
to a class of mathematicians but I suspect the discussion would be
very different.)
My first thought was "no, it's the same", but on reflexion,
and AFAIR, our mathematicians simply accepted what I told them,
which is essentially what
is at
http://www.cuboid.me.uk/anw/G12FCO/lect17.html
[second half, but see esp the last paragraph] and
http://www.cuboid.me.uk/anw/G12FCO/lect18.html
For these cases, we can turn to our second weapon -- emulation. We
want to know whether a program halts, so we try it. If it halts, then
we know the answer. If it doesn't halt, then `it must be in a loop',
so we monitor its state and `detect the loop'. Sadly, although this
is in one sense correct, it is a false dichotomy. At any given moment
as the emulation proceeds, we are in one of not two but three states:
the program has halted, or it is looping, or it is still running and
has not yet entered a loop. It's the third case that kills us -- we
just have to keep going, and wait for one of the other two things to
happen. The trouble is that it may be that neither of them ever
happens -- which is why `it must be in a loop' was in quotes above.
It is not considered correctly.
(a) the program has halted
(b) the program is still running
(c) the program matched an infinite behavior pattern
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
Any competent software engineer can verify that H(P,P)==0
for the above behavior pattern. (The entire research scope)
As detailed in my paper:
Halting problem undecidability and infinitely nested simulation (V5)
https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5
The proofs you are attempting to refute do not contain the infinite
behaviour pattern you describe;
you have been told this multiple times
now and keep ignoring it:
is this because you have actually given up
trying to refute those proofs?
/Flibble
On 6/2/2022 1:12 PM, Andy Walker wrote:
On 02/06/2022 17:21, Ben wrote:
[...] We know simulation can't be
used to decide halting, and we know that there are only two ways a
decider that tries to do so can be wrong. Both come up every time
this is taught to a class of programmers. (I've never taught it
to a class of mathematicians but I suspect the discussion would be
very different.)
My first thought was "no, it's the same", but on reflexion,
and AFAIR, our mathematicians simply accepted what I told them,
which is essentially what
is at
http://www.cuboid.me.uk/anw/G12FCO/lect17.html
[second half, but see esp the last paragraph] and
http://www.cuboid.me.uk/anw/G12FCO/lect18.html
For these cases, we can turn to our second weapon -- emulation. We
want to know whether a program halts, so we try it. If it halts, then
we know the answer. If it doesn't halt, then `it must be in a loop',
so we monitor its state and `detect the loop'. Sadly, although this
is in one sense correct, it is a false dichotomy. At any given moment
as the emulation proceeds, we are in one of not two but three states:
the program has halted, or it is looping, or it is still running and
has not yet entered a loop. It's the third case that kills us -- we
just have to keep going, and wait for one of the other two things to
happen. The trouble is that it may be that neither of them ever
happens -- which is why `it must be in a loop' was in quotes above.
It is not considered correctly.
(a) the program has halted
(b) the program is still running
(c) the program matched an infinite behavior pattern
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
Any competent software engineer can verify that H(P,P)==0
for the above behavior pattern. (The entire research scope)
As detailed in my paper:
Halting problem undecidability and infinitely nested simulation (V5)
https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5
On 6/2/2022 11:21 AM, Ben wrote:
Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
On Wednesday, 1 June 2022 at 20:03:43 UTC+1, Ben wrote:
Malcolm McLean <malcolm.ar...@gmail.com> writes:The "simulating halt decider" will fail when fed H_Hat, not because of
And actually, what you have done is construct a simulatingWhat? H_Hat(H_Hat) halts because H(H_Hat, H_Hat) == 0 so, yes, no loop >>>> is involved, but that's not interesting.
attempted halt
decider, which fails on H_Hat, for reasons unrelated to the invert
loop.
So you have actually achieved something of interest, if you could only >>>>> recognise that.What do you think is new or interesting here? I can't see anything new >>>> or interesting here at all.
the invert step, but because it can't solve the simulation of H.
What's new or interesting about that? A simulating partial halt decider
really only has only two ways to be wrong: fail to return a result or
incorrectly decide some halting computations as non-halting (ignoring
cases where it's designed to be deliberately wrong unnecessarily).
And H_Hat never has anything to do with why a decider is wrong because
we can show that any purported halt decider must get infinitely many
instances wrong, so there will be an abundance of examples that have
nothing to do with H_Hat.
But none of this is what PO is claiming. He claims H is right to be
wrong so you have your work cut out if you want to get him to accept
that H really is wrong, even if you find the reason interesting.
NO I AM NOT SAYING THAT AT ALL PLEASE PAY MUCH CLOSER ATTENTION I HAVE
HAD TO REPEAT MYSELF HUNDREDS OF TIMES AND EVERYONE CONSISTENTLY IGNORES
MY CORRECTIONS TO THEIR FALSE ASSUMPTIONS AND MISCONCEPTIONS.
It is an easily verified fact that the correctly simulated input to
H(P,P) never reaches its "ret" instruction therefore even when the
simulation is aborted P did not halt and never would halt.
This conclusively proves that H(P,P)==0 to anyone that is merely
a fully competent software engineer having the required prerequisites
of C, x86, how C translates to x86, and what x86 emulation is.
LIARS AND IDIOTS DENY THE TRUTH OF THIS
It is completely obvious that when H(P,P) correctly emulates its input
that it must emulate the first seven instructions of P. Because the
seventh instruction repeats this process we can know with complete
certainty that the emulated P never reaches its find “ret” instruction, thus never halts.
Because Ben very very persistently refused to confirm the truth of this
I mistook him for a liar. When he acknowledged that he saw no evidence
that it is not true I acknowledged that my attribution of liar was
incorrect.
That's inherent in the way
it is set up - it can only terminate if it detects that the series of
nested
simulations is non-terminating, in which case it becomes terminating.
No, it terminates because it /incorrectly/ concludes that the nested
simulations are non-terminating. PO's silly argument is that this
conclusion is not wrong because the nested simulations /would/ be
non-terminating if they were not terminated. Go figure.
I don't think anyone has actually pointed that out before. It's not
going to
revolutionise computer science. But it is an interesting observation.
Why would anyone want to point this out? We know simulation can't be
used to decide halting, and we know that there are only two ways a
decider that tries to do so can be wrong. Both come up every time this
is taught to a class of programmers. (I've never taught it to a class
of mathematicians but I suspect the discussion would be very different.)
On 6/2/2022 11:32 AM, Mike Terry wrote:
On 02/06/2022 12:19, Malcolm McLean wrote:
On Wednesday, 1 June 2022 at 20:03:43 UTC+1, Ben wrote:
Malcolm McLean <malcolm.ar...@gmail.com> writes:The "simulating halt decider" will fail when fed H_Hat, not because
And actually, what you have done is construct a simulatingWhat? H_Hat(H_Hat) halts because H(H_Hat, H_Hat) == 0 so, yes, no loop >>>> is involved, but that's not interesting.
attempted halt
decider, which fails on H_Hat, for reasons unrelated to the invert
loop.
So you have actually achieved something of interest, if you could only >>>>> recognise that.What do you think is new or interesting here? I can't see anything new >>>> or interesting here at all.
of the invert
step, but because it can't solve the simulation of H. That's inherent
in the way
it is set up - it can only terminate if it detects that the series of
nested
simulations is non-terminating, in which case it becomes terminating.
..in which case it becomes terminating BECAUSE OF THE INVERT STEP.
AS I HAVE PROVEN MANY HUNDREDS OF TIMES THE SIMULATED INPUT TO H(P,P)
NEVER REACHES THE INVERT STEP.
It is an easily verified fact that the correctly simulated input to
H(P,P) never reaches its "ret" instruction therefore even when the
simulation is aborted P did not halt and never would halt.
This conclusively proves that H(P,P)==0 to anyone that is merely
a fully competent software engineer having the required prerequisites
of C, x86, how C translates to x86, and what x86 emulation is.
LIARS AND IDIOTS DENY THE TRUTH OF THIS
It is completely obvious that when H(P,P) correctly emulates its input
that it must emulate the first seven instructions of P. Because the
seventh instruction repeats this process we can know with complete
certainty that the emulated P never reaches its find “ret” instruction, thus never halts.
On 6/2/2022 6:38 PM, Mr Flibble wrote:
On Thu, 2 Jun 2022 15:47:22 -0500
olcott <NoOne@NoWhere.com> wrote:
On 6/2/2022 1:12 PM, Andy Walker wrote:
On 02/06/2022 17:21, Ben wrote:
[...] We know simulation can't be
used to decide halting, and we know that there are only two ways a
decider that tries to do so can be wrong. Both come up every time
this is taught to a class of programmers. (I've never taught it
to a class of mathematicians but I suspect the discussion would be
very different.)
My first thought was "no, it's the same", but on reflexion, >>>> and AFAIR, our mathematicians simply accepted what I told them,
which is essentially what
is at
http://www.cuboid.me.uk/anw/G12FCO/lect17.html
[second half, but see esp the last paragraph] and
http://www.cuboid.me.uk/anw/G12FCO/lect18.html
For these cases, we can turn to our second weapon -- emulation. We
want to know whether a program halts, so we try it. If it halts, then
we know the answer. If it doesn't halt, then `it must be in a loop',
so we monitor its state and `detect the loop'. Sadly, although this
is in one sense correct, it is a false dichotomy. At any given moment
as the emulation proceeds, we are in one of not two but three states:
the program has halted, or it is looping, or it is still running and
has not yet entered a loop. It's the third case that kills us -- we
just have to keep going, and wait for one of the other two things to
happen. The trouble is that it may be that neither of them ever
happens -- which is why `it must be in a loop' was in quotes above.
It is not considered correctly.
(a) the program has halted
(b) the program is still running
(c) the program matched an infinite behavior pattern
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
Any competent software engineer can verify that H(P,P)==0
for the above behavior pattern. (The entire research scope)
As detailed in my paper:
Halting problem undecidability and infinitely nested simulation (V5)
https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5
The proofs you are attempting to refute do not contain the infinite
behaviour pattern you describe;
The correctly simulated input to a simulating halt decider never reaches
the final instruction of this simulated input thus is unequivocally non-halting.
Halting does not mean stopped running, it means terminated normally., so we can
Whether or not this simulated input specifies infinite behavior is a
matter of how one defines one's terms and makes no difference because
the behavior that it does exhibit is still correctly construed as
non-halting even after its simulation has been aborted.
you have been told this multiple times
now and keep ignoring it:
Every time that I correct my reviewers false assumptions and
misconceptions they always make sure to not read a single word of what I
have said.
It is always blah blah blah we know you must be wrong so there is no
sense in reading what your reply.
is this because you have actually given up
trying to refute those proofs?
/Flibble
On 6/2/2022 2:00 PM, Ben wrote:
Andy Walker <anw@cuboid.co.uk> writes:
On 02/06/2022 17:21, Ben wrote:
[...] We know simulation can't be
used to decide halting, and we know that there are only two ways a
decider that tries to do so can be wrong. Both come up every time this >>>> is taught to a class of programmers. (I've never taught it to a class >>>> of mathematicians but I suspect the discussion would be very
different.)
My first thought was "no, it's the same", but on reflexion, and
AFAIR,
our mathematicians simply accepted what I told them, which is
essentially what
is at
http://www.cuboid.me.uk/anw/G12FCO/lect17.html
[second half, but see esp the last paragraph] and
http://www.cuboid.me.uk/anw/G12FCO/lect18.html
I see your notes are an explicit counterexample to PO's claims that
emulation is never considered!
For these cases, we can turn to our second weapon -- emulation. We want
to know whether a program halts, so we try it. If it halts, then we know
the answer. If it doesn't halt, then `it must be in a loop', so we
monitor its state and `detect the loop'. Sadly, although this is in one
sense correct, it is a false dichotomy. At any given moment as the
emulation proceeds, we are in one of not two but three states: the
program has halted, or it is looping, or it is still running and has not
yet entered a loop. It's the third case that kills us -- we just have to
keep going, and wait for one of the other two things to happen. The
trouble is that it may be that neither of them ever happens -- which is
why `it must be in a loop' was in quotes above.
It is not considered correctly.
(a) the program has halted
(b) the program is still running
(c) the program matched an infinite behavior pattern
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
H(P,P)==0 for the above behavior pattern. (The entire research scope)
[both lectures from a module that I gave many moons ago]. We got pretty >>> bright students, among the top four or five cohorts in the UK at that
time
[1990s] [but that was our high point, even beating Oxford one year],
and of
course many of them went into IT as a career. They found
NP-completeness
much harder than UTMs, HP and related stuff.
We got pretty bright students too. Bright students ask good questions
but eventually (rapidly even) settle the matter to their own
satisfaction.
And I agree that complexity is more... complex. The details become so
very significant in complexity theory. One of the depressing things
about these endless threads is that this is not a complex theorem.
On 02/06/2022 17:21, Ben wrote:
[...] We know simulation can't be
used to decide halting, and we know that there are only two ways a
decider that tries to do so can be wrong. Both come up every time this
is taught to a class of programmers. (I've never taught it to a class
of mathematicians but I suspect the discussion would be very different.)
My first thought was "no, it's the same", but on reflexion, and AFAIR,
our mathematicians simply accepted what I told them, which is
essentially what
is at
http://www.cuboid.me.uk/anw/G12FCO/lect17.html
[second half, but see esp the last paragraph] and
http://www.cuboid.me.uk/anw/G12FCO/lect18.html
[both lectures from a module that I gave many moons ago]. We got pretty bright students, among the top four or five cohorts in the UK at that time [1990s] [but that was our high point, even beating Oxford one year], and of course many of them went into IT as a career. They found NP-completeness much harder than UTMs, HP and related stuff.
[The code G12FCO means G1 -- maths, 2 -- second year, FCO -- Formal Computation.]
On 6/2/2022 1:12 PM, Andy Walker wrote:
On 02/06/2022 17:21, Ben wrote:
[...] We know simulation can't be
used to decide halting, and we know that there are only two ways a
decider that tries to do so can be wrong. Both come up every time this >>> is taught to a class of programmers. (I've never taught it to a class
of mathematicians but I suspect the discussion would be very different.)
My first thought was "no, it's the same", but on reflexion, and
AFAIR,
our mathematicians simply accepted what I told them, which is
essentially what
is at
http://www.cuboid.me.uk/anw/G12FCO/lect17.html
[second half, but see esp the last paragraph] and
http://www.cuboid.me.uk/anw/G12FCO/lect18.html
[both lectures from a module that I gave many moons ago]. We got pretty
bright students, among the top four or five cohorts in the UK at that
time
[1990s] [but that was our high point, even beating Oxford one year],
and of
course many of them went into IT as a career. They found NP-completeness >> much harder than UTMs, HP and related stuff.
[The code G12FCO means G1 -- maths, 2 -- second year, FCO -- Formal
Computation.]
At any given moment as the emulation proceeds, we are in one of not two
but three states: the program has halted, or it is looping, or it is
still running and has not yet entered a loop. It's the third case that
kills us -- we just have to keep going, and wait for one of the other
two things to happen. The trouble is that it may be that neither of them
ever happens -- which is why `it must be in a loop' was in quotes above.
Andy Walker did provide a fundamentally flawed and totally shallow
analysis of an simulating halt decider.
At any given moment as the emulation proceeds,
we are in one of not two but three states:
(a) The program has halted,
(b) It is still running.
(c) IT HAS MATCHED AN INFINITE BEHAVIOR PATTERN
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
return;
}
The above matches (c) for infinitely nested simulation.
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 384 |
| Nodes: | 16 (3 / 13) |
| Uptime: | 60:21:09 |
| Calls: | 8,173 |
| Calls today: | 5 |
| Files: | 13,113 |
| Messages: | 5,864,381 |