Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: sci.logic
Subject: Re: Why does Olcott care about simulation, anyway?
Date: Mon, 03 Jun 2024 12:11:04 +0800
Organization: A noiseless patient Spider
Lines: 196
Message-ID: <75edc383cda76101a801e8926f3a9b20e7716387.camel@gmail.com>
References: <v3j20v$3gm10$2@dont-email.me>
	 <J_CdnTaA96jxpcD7nZ2dnZfqnPudnZ2d@brightview.co.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Mon, 03 Jun 2024 06:11:06 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="53ecd3a08a774183dc348db4349cad0c";
	logging-data="3942491"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18HdWwszPaNJmWahqo1/nQ5"
User-Agent: Evolution 3.50.2 (3.50.2-1.fc39)
Cancel-Lock: sha1:KZiCasxJBaMyYJDNrPKQ6YEEbsI=
In-Reply-To: <J_CdnTaA96jxpcD7nZ2dnZfqnPudnZ2d@brightview.co.uk>
Bytes: 10132

On Mon, 2024-06-03 at 04:28 +0100, Mike Terry wrote:
> On 03/06/2024 01:16, immibis wrote:
> > The halting problem says you can't find a Turing machine that tells whe=
ther executing each other=20
> > Turing machine will halt. Simulation has nothing to do with the questio=
n.
>=20
> Background:
>=20
> PO claims to have refuted the common HP proof, e.g. as covered in the Lin=
z book "An Introduction to=20
> Formal Languages and Automata".=C2=A0 PO occasionally posts a link to a P=
DF containing an extract of the=20
> 5 or so pages of the book containing the proof, but I expect you have acc=
ess to this or equivalent.
>=20
> In a nutshell, the proof goes:
> -=C2=A0 Suppose H is a TM Halt decider that decides for any input <P><I> =
whether
> =C2=A0=C2=A0=C2=A0 TM P run with input I on its input tape halts.
> =C2=A0=C2=A0=C2=A0 [<P> is the string representation of the actual TM P, =
and
> =C2=A0=C2=A0=C2=A0=C2=A0 <I> is the string representation of input tape I=
]
> -=C2=A0 Construct from H a new TM H^ using the mechanical process describ=
ed in the proof.
> =C2=A0=C2=A0=C2=A0 If H exists, then its corresponding H^ also exists.
> -=C2=A0 Show that the construction of H^ ensures that:
> =C2=A0=C2=A0=C2=A0 -=C2=A0 if H decides input <H^><H^> (representing H^ r=
unning with input <H^>) halts,
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 then that implies that H^ running wi=
th input <H^> never halts
> =C2=A0=C2=A0=C2=A0 -=C2=A0 if H decides input <H^><H^> never halts,
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 then that implies H^ running with in=
put <H^> halts
> =C2=A0=C2=A0=C2=A0 I.e. either way, H decides the specific input <H^><H^>=
 incorrectly, contradicting
> =C2=A0=C2=A0=C2=A0 the initial assumption that H is a halt decider.
> -=C2=A0 So no halt decider exists.=C2=A0 (Every proposed halt decider dec=
ides at least one input case
> =C2=A0=C2=A0=C2=A0 incorrectly, viz input <H^><H^>.)
>=20
> PO basically claimed he had a fully coded TM H, which CORRECTLY decides i=
ts "nemesis" input=20
> <H^><H^>, contradicting the logic of the Linz proof [without pointing out=
 any actual mistake in the=20
> Linz proof].=C2=A0 Given most people here understand the Linz proof well =
enough to see it is basically=20
> sound, people were sceptical!
>=20
> It turned out PO was lying about the fully coded TM, and in fact what he =
actually had was the idea=20
> behind a C program which would "prove" his idea.=C2=A0 A couple of years(=
?) later he actually completed=20
> his C program and his x86utm.exe which would simulate the x86 code of his=
 H and H^ to "prove" his=20
> claim.=C2=A0 His equivalent of Linz H is his C function H or HH, and his =
equivalent of Linz H^ is his D=20
> or DD respectively.=C2=A0 (They run under x86utm.exe and are not Windows/=
Unix executables.)
>=20
> H/HH use PARTIAL simulation of their input to decide halting/non-halting,=
 returning
> 0 or 1 to communicate their decision.=C2=A0 As you correctly point out, t=
o the HP proof simulation is=20
> quite irrelevant, being just one kind of data manipulation that H may per=
form on its input string=20
> <P><I> before it decides the halting status.=C2=A0 So the Linz HP proof c=
overs such H, no problem.
> [I put PARTIAL in caps, just because there seems to be some confusion in =
recent threads as to what=20
> PO means by "simulation".=C2=A0 He doesn't say it explicitly, despite sug=
gestions to this effect, but he=20
> always means what might be called /partial/ simulation.]
>=20
> PO believes that by (partially) simulating the computation corresponding =
to the input <P><I> [i.e.=20
> calculating the successive x86 instruction steps of the computation P(I)]=
 and monitoring the=20
> progress of virtual x86 state changes (like instruction address and op-co=
de and so on) H could spot=20
> some pattern that reveals whether computation P(I) halts or not.=C2=A0 At=
 this point in the partial=20
> simulation, his H would stop simulating (aka "abort" the simulation) and =
return the appropriate halt
> status for input <P><I>.
>=20
> Nothing remarkable so far!=C2=A0 Clearly a tight-loop in P /can/ be detec=
ted in this fashion, so /some/=20
> <P><I> inputs /can/ be correctly determined like this.=C2=A0 The PO claim=
 however is that the specific=20
> input <H^><H^> is correctly decided by his H.=C2=A0 In C terms those corr=
espond to H(D,D) correctly=20
> returning the halt status of computation D(D).=C2=A0 [PO would probably d=
ispute this, because he doesn't=20
> properly understand halting or the HP generally, or in fact pretty much /=
any abstract concept/ ]
>=20
> So of great interest in all this would be: what in fact is the halt statu=
s of PO's contoversial=20
> D(D), and what in fact does his H(D,D) return as the halt status of that =
input, right?
>=20
> PO's D(D) halts, as illustrated in various traces that have been posted h=
ere.
> PO's H(D,D) returns 0 : [NOT halting] also as illustrated in various trac=
es.
> i.e. exactly as the Linz proof claims.=C2=A0 PO has acknowledged both the=
se results.=C2=A0 Same for the HH/DD=20
> variants.
>=20
> You might imagine that's the end of the matter - PO failed.=C2=A0 :)
>=20
> That's right, but PO just carries on anyway!=C2=A0 Where 99.99% students =
would think "damn, where did I=20
> go wrong" and go back over their thinking to identify their mistake [aka =
"learn" from the whole=20
> episode], PO just doubles down on his original claim, modifying it to [so=
mething barely coherent and
> clearly not refuting any HP proof].=C2=A0 I can't even bring myself to tr=
y to explain exactly what PO=20
> claims these days.=C2=A0 IT DOES NOT MATTER unless you really feel a need=
 to "understand" PO and where he
> goes wrong.
>=20
> And while we're here, "arguing" with PO about anything is also pointless =
:)=C2=A0 in so far that:
>=20
> -=C2=A0 PO is /unable/ to understand your arguments or even the definitio=
n of the
> =C2=A0=C2=A0=C2=A0 terms you use.=C2=A0 And he is incapable of logically =
explaining his own position.
> =C2=A0=C2=A0=C2=A0 In the end he just believes what he thinks is right (h=
is intuitions) regardless
> =C2=A0=C2=A0=C2=A0 of any "logic" aka "extraneous complexity" that respon=
ders employ!=C2=A0 I put this down
> =C2=A0=C2=A0=C2=A0 to some physical brain-wiring issue that PO has, meani=
ng he cannot cope with
> =C2=A0=C2=A0=C2=A0 abstract concepts like others can.=C2=A0 [...but who k=
nows at that level...]
> =C2=A0=C2=A0=C2=A0 NOTE: it's not that PO isn't concentrating, or that pe=
ople aren't explaining
> =C2=A0=C2=A0=C2=A0 clearly enough.=C2=A0 I know there's a tendancy for po=
sters to think that the lack of
> =C2=A0=C2=A0=C2=A0 genuine communication with PO is their fault, or at le=
ast something they can address
> =C2=A0=C2=A0=C2=A0 somehow.=C2=A0 It's not.
> -=C2=A0 So people here can't "help" him by getting him to understand his =
mistakes - that's
> =C2=A0=C2=A0=C2=A0 just not going to happen.=C2=A0 PO will die firmly bel=
ieving that he is an
> =C2=A0=C2=A0=C2=A0 unacknowledged genius with superior powers of concentr=
ation/reasoning to all
> =C2=A0=C2=A0=C2=A0 of us.=C2=A0 That may seem UNJUST, but it is unavoidab=
le, and really DOESN'T MATTER;
> =C2=A0=C2=A0=C2=A0 When PO dies (as everyone dies) the world will just ca=
rry on as it does.
> -=C2=A0 no "innocent student" is going to read PO's claims and think "aha=
, looks like
> =C2=A0=C2=A0=C2=A0 the Halting Problem is decideable after all!=C2=A0 I'l=
l use that in my exams next week
> =C2=A0=C2=A0=C2=A0 to gain extra points"!=C2=A0 [Or if they do, they'll g=
et what they deserve :)]
> =C2=A0=C2=A0=C2=A0 People who understand HP quickly figure out PO is just=
 a crank, although it may take some
> =C2=A0=C2=A0=C2=A0 time for them to see the bigger picture of what PO is =
claiming etc. if they get that far.
> =C2=A0=C2=A0=C2=A0 Crankhood can be quickly decided due to PO's constant =
use of "duffer phrasing"
> =C2=A0=C2=A0=C2=A0 and general lack of coherency in everything he posts -=
 actual geniuses don't do that.
>=20
> So really, there's no /need/ to "refute" everything he says - the end res=
ult will be exactly the=20
> same as just ignoring him, BUT WITH THE LATTER ONLY NEEDING 0.1% OF THE E=
FFORT and eliminating 99.9%
> of the posting clutter in these newsgroups.=C2=A0 [ok, comp.theory will d=
ie pretty quickly, but it is not
> discussing anything useful, so that's ok for most people... (with some re=
========== REMAINDER OF ARTICLE TRUNCATED ==========