Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met

Liste des GroupesRevenir à theory 
Sujet : Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met
De : rjh (at) *nospam* cpax.org.uk (Richard Heathfield)
Groupes : comp.theory
Date : 20. May 2025, 05:59:47
Autres entêtes
Organisation : Fix this later
Message-ID : <100h284$236kl$1@dont-email.me>
References : 1 2 3 4 5 6 7 8 9 10 11 12 13 14
User-Agent : Mozilla Thunderbird
On 20/05/2025 05:10, olcott wrote:
On 5/19/2025 5:12 AM, Mikko wrote:
On 2025-05-18 19:18:21 +0000, olcott said:
<snip>

When the hypothetical H never aborts its simulated D then:
(a) Simulated D  NEVER HALTS
(b) Executed D() NEVER HALTS
(c) Executed H() NEVER HALTS
(d) Everything that H calls NEVER HALTS
>
You forgot
(e) H does not report
>
 HHH is required to report, that is why it
must always report on the behavior of the
hypothetical H/D pair and not the actual
behavior of the actual H/D pair for every
non-terminating input.
It's quite true that the reporter is required to report, and this is precisely where the whole idea of simulation proves to be rather wobbly. Clearly, in cases where the simulated program never terminates the simulator cannot run to completion if the reporter is ever to deliver its report. The reporter is therefore required to report a guess.
This guess could be extremely sophisticated, or it might be very naive. For example, one could devise an abstract syntax tree from the program, maybe prune it of statements that can be shown not to affect the halt state, and take a long hard look at the remaining behaviour using clever techniques yet to be discovered by a computer scientist not yet born; or one might simply compare the state of the simulation to all previous states and look for an exact match because a state that has recurred once may very well recur again, and again, and again... Such an event certainly makes a guess of 'never halts' extremely seductive, although of course it remains a mere guess.
Unfortunately, as well as making rapidly increasing demands on memory this method makes the entirely unwarranted assumption that the input tape can be ignored. Who is to say that the simulated program is not simply waiting for some specific symbol to appear under the tape's read head before it shakes off its torpor and continues on its merry way?
And so, no matter how long the simulation continues, the simulator can never with certainty deduce that the program will never halt. It must guess, and guessing means sometimes guessing /wrong/.
Unfortunately, guessing wrong isn't one of the options.
The question is whether an algorithm exists for determining whether an arbitrary program halts given arbitrary input.
The question is NOT whether an algorithm exists for determining whether an arbitrary program MIGHT halt given arbitrary input.
There is no room here for guessing, and simulation is therefore a theoretical dead end.
No. There is no substitute for analysing the tapes to get at the input and the program instructions themselves, whether they be in the expansive form of source code or the nitty gritty nuts and bolts of machine code. And the moment we take the analytical route, we run headlong into Turing's twist, and we're already dead in the water.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

Date Sujet#  Auteur
15 May 25 * Overcoming the proof of undecidability of the Halting Problem by a simple example in C231olcott
15 May 25 +* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C18olcott
15 May 25 i+* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C12olcott
16 May 25 ii+* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C7olcott
16 May 25 iii+* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C2olcott
16 May 25 iiii`- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Richard Damon
16 May 25 iii`* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C4Mikko
16 May 25 iii `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C3olcott
16 May 25 iii  +- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Richard Damon
17 May 25 iii  `- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Mikko
16 May 25 ii`* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C4Mikko
16 May 25 ii `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C3olcott
16 May 25 ii  +- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Richard Damon
17 May 25 ii  `- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Mikko
16 May 25 i`* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C5Mikko
16 May 25 i `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C4olcott
16 May 25 i  +- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1olcott
16 May 25 i  +- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Richard Damon
17 May 25 i  `- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Mikko
16 May 25 `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C212olcott
16 May 25  +* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C61Richard Heathfield
16 May 25  i`* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C60olcott
16 May 25  i +* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C3Richard Heathfield
16 May 25  i i`* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C2olcott
16 May 25  i i `- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Richard Heathfield
16 May 25  i `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C56Mikko
16 May 25  i  `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C55olcott
16 May 25  i   +* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C29Richard Heathfield
17 May 25  i   i`* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C28olcott
17 May 25  i   i +* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C6Richard Damon
17 May 25  i   i i`* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C5olcott
17 May 25  i   i i `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C4Richard Damon
17 May 25  i   i i  `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C3olcott
17 May 25  i   i i   +- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Fred. Zwarts
17 May 25  i   i i   `- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Richard Damon
17 May 25  i   i `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C21Richard Heathfield
17 May 25  i   i  `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C20olcott
17 May 25  i   i   +* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C15Richard Heathfield
17 May 25  i   i   i`* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C14olcott
17 May 25  i   i   i `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C13Richard Heathfield
17 May 25  i   i   i  `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C12olcott
17 May 25  i   i   i   +* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C5Richard Heathfield
17 May 25  i   i   i   i`* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C4olcott
17 May 25  i   i   i   i `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C3Richard Heathfield
17 May 25  i   i   i   i  `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C2olcott
17 May 25  i   i   i   i   `- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Richard Heathfield
17 May 25  i   i   i   `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C6Richard Damon
18 May 25  i   i   i    `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C5Richard Heathfield
19 May 25  i   i   i     `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C4Mikko
19 May 25  i   i   i      `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C3Richard Heathfield
19 May 25  i   i   i       `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C2Mikko
19 May 25  i   i   i        `- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Richard Heathfield
17 May 25  i   i   `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C4Richard Damon
17 May 25  i   i    `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C3olcott
17 May 25  i   i     +- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Fred. Zwarts
17 May 25  i   i     `- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Richard Damon
16 May 25  i   +* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C3Richard Damon
17 May 25  i   i`* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C2olcott
17 May 25  i   i `- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Richard Damon
17 May 25  i   `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C22Mikko
18 May 25  i    `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C21Richard Heathfield
18 May 25  i     `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C20Ben Bacarisse
19 May 25  i      +* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C18Richard Heathfield
19 May 25  i      i`* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C17Ben Bacarisse
19 May 25  i      i `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C16olcott
19 May 25  i      i  +* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C14Richard Heathfield
19 May 25  i      i  i`* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C13olcott
19 May 25  i      i  i +* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C11Richard Heathfield
19 May 25  i      i  i i+* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C8Richard Heathfield
19 May 25  i      i  i ii`* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C7Richard Heathfield
19 May 25  i      i  i ii `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C6olcott
19 May 25  i      i  i ii  +* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C4Richard Heathfield
19 May 25  i      i  i ii  i`* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C3olcott
19 May 25  i      i  i ii  i +- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Richard Heathfield
19 May 25  i      i  i ii  i `- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Mikko
19 May 25  i      i  i ii  `- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Richard Damon
19 May 25  i      i  i i+- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Mikko
19 May 25  i      i  i i`- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Richard Damon
19 May 25  i      i  i `- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Mikko
19 May 25  i      i  `- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Mikko
19 May 25  i      `- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Mikko
16 May 25  +* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C5Richard Damon
16 May 25  i`* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C4olcott
16 May 25  i `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C3Richard Damon
16 May 25  i  `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C2olcott
16 May 25  i   `- Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C1Richard Damon
16 May 25  `* Re: Overcoming the proof of undecidability of the Halting Problem by a simple example in C145Mikko
16 May 25   `* Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met144olcott
17 May 25    `* Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met143Mikko
17 May 25     `* Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met142olcott
17 May 25      +* Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met3Richard Damon
17 May 25      i`* Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met2olcott
18 May 25      i `- Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met1Mikko
18 May 25      `* Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met138Mikko
18 May 25       +* Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met131Mike Terry
18 May 25       i`* Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met130olcott
18 May 25       i +* Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met28joes
18 May 25       i i`* Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met27olcott
18 May 25       i i +- Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met1Richard Damon
19 May 25       i i `* Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met25Mikko
20 May 25       i i  `* Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met24olcott
18 May 25       i `* Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met101Richard Damon
18 May 25       `* Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met6olcott

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal