XPost: comp.theory, comp.software-eng, sci.logic
On 9/2/2021 11:10 AM, Malcolm McLean wrote:
On Thursday, 2 September 2021 at 16:19:57 UTC+1, Ben Bacarisse wrote:
olcott <No...@NoWhere.com> writes:
On 9/2/2021 4:40 AM, Malcolm McLean wrote:
It's common ground that H_Hat<H_Hat> halts, and H<H_Hat><H_Hat>
returns false (non-halting). But the claim is that H is nevertheless correct.
We have to adapt the halt deciding criteria so that it can correctly
handle pathological inputs.
Explicit admission (again) that you are not deciding halting. Does
anyone care about the criterion you are applying and confusing calling
halting? I don't think so.
Pathological Input to a halt decider is stipulated to mean any input
that was defined to do the opposite of whatever its corresponding halt
decider decides as Sipser describes:
Now we construct a new Turing machine D with H as a subroutine.
This new TM calls H to determine what M does when the input to M
is its own description ⟨M⟩. Once D has determined this information,
it does the opposite. (Sipser:1997:165)
There is no algorithm that can detect what you call "Pathological
Input". You keep quoting me saying that, so presumably you agree with
me. Why are you wasting time on an undecidable set ("pathological
inputs") that is not even interesting?
You've nailed it exactly. PO has said, in effect, "Why not detect the self-contradictory
case and handle it specially?". According to you, when you teach this material
to computer science freshmen, there's always someone who raises that question.
Pathological Input to a halt decider is stipulated to mean any input
that was defined to do the opposite of whatever its corresponding halt
decider decides as Sipser describes:
Now we construct a new Turing machine D with H as a subroutine.
This new TM calls H to determine what M does when the input to M
is its own description ⟨M⟩. Once D has determined this information,
it does the opposite. (Sipser:1997:165)
This criteria merely relies on the fact that the UTM simulation of a
machine description of a machine is computationally equivalent to the
direct execution of this same machine:
Simulating Halt Decider Theorem (Olcott 2020):
A simulating halt decider correctly decides that any input that never
halts unless the simulating halt decider aborts its simulation of this
input is an input that never halts.
The above criteria handles all inputs correctly including pathological
inputs.
Because the halt decider acts as a pure simulator until after its halt
status decision has been made the pathological feedback loop has been eliminated from the halt status decision of pathological inputs.
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)