Liste des Groupes | Revenir à theory |
On 5/31/2025 8:37 AM, Mike Terry wrote:No, but he proved that there are problems that are not Turing decidable.On 31/05/2025 11:03, Richard Heathfield wrote:Turing wasn't even dealing with halting.On 31/05/2025 10:42, Mikko wrote:More like:On 2025-05-30 17:27:05 +0000, olcott said:<snip>
On 5/30/2025 12:06 PM, Richard Heathfield wrote:
Indeed. In fact, if I'm reading Mr Olcott's retort correctly...We can apply Truing'c construction to every Truing machine andAs far as I can recall, Olcott's ramblings never go within discus- throwing distance of a potentially erroneous step.There is no *INPUT* D to termination analyzer H
that can possibly do the opposite of whatever
value that H returns.
prove that no Turing machine is a halting decider. With a
similar construction many other problems about Turing machine
behaviour can be proven uncomputable, too.
Turing: imagine a program P...
Turing: ...argument goes here...
Turing: ...and it turns out that P can't exist.
Olcott: Turing is wrong, because P can't exist.
I /seeeeee.../
Turing: imagine a program P...
Turing: ...modify P as follows to create D...
Turing: ...argument goes here...
Turing: ...so P decides D's halting incorrectly
Turing: ...and so P is not a halt decider.
Olcott: Turing is wrong, because *D* can't exist.
I /seeeeee.../
Mike.
*Here is the orignal Linz proof*Linz' presentation of the proof is not as good as it could be.
https://www.liarparadox.org/Linz_Proof.pdf
In the following embedded_H is P and ⟨Ĥ⟩ is DThe above is nonsense because there are two main clauses with
When Ĥ is applied to ⟨Ĥ⟩
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
Les messages affichés proviennent d'usenet.