Message-ID:

No, that'd be silly. -- Larry Wall in <199710221710.KAA24242@wall.org>

devel / comp.theory / Good news everyone - the halting problem has been solved! (again)

Good news everyone - the halting problem has been solved! (again)

<uls6cp$27po$3@dont-email.me>

https://www.novabbs.com/devel/article-flat.php?id=49933&group=comp.theory#49933

Path: i2pn2.org!i2pn.org!paganini.bofh.team!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: new...@immibis.com (immibis)
Newsgroups: comp.theory
Subject: Good news everyone - the halting problem has been solved! (again)
Date: Tue, 19 Dec 2023 14:38:33 +0100
Organization: A noiseless patient Spider
Lines: 12
Message-ID: <uls6cp$27po$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 19 Dec 2023 13:38:33 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="c95b9f06949c68a7be13f701a542acec";
logging-data="73528"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+akG1N05kmTs3ZYm4K+z/Y"
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
Thunderbird/102.14.0
Cancel-Lock: sha1:eEjfInfv32c5uvbPpq+GO/1x+V0=
Content-Language: en-US

by: immibis - Tue, 19 Dec 2023 13:38 UTC

Suppose we possess a halting decider which is always right.
We feed it a counterexample program which it says does not halt.
We run the program and it halts.
Because the halting decider is always right, we know the program does
not halt.
Because we ran the program, we know it halts.
Therefore the program halts iff it does not halt.
A prediction of non-halting is therefore a prediction of halting, which
is a correct prediction. The halting decider has solved the halting problem.

Constructing such a halting decider and observing the unwinding of
reality is left an exercise to the reader.

Subject	Author
Good news everyone - the halting problem has been solved! (again)	immibis