Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

We have a equal opportunity Calculus class -- it's fully integrated.


computers / comp.ai.philosophy / Re: Halt deciders

SubjectAuthor
o Re: Halt decidersolcott

1
Re: Halt deciders

<tijp2v$gq2$2@gioia.aioe.org>

 copy mid

https://www.novabbs.com/computers/article-flat.php?id=9906&group=comp.ai.philosophy#9906

 copy link   Newsgroups: comp.theory sci.logic comp.ai.philosophy
Path: i2pn2.org!i2pn.org!aioe.org!/GRMamn3ov7sGOWkEuxPQw.user.46.165.242.91.POSTED!not-for-mail
From: none...@beez-waxes.com (olcott)
Newsgroups: comp.theory,sci.logic,comp.ai.philosophy
Subject: Re: Halt deciders
Date: Mon, 17 Oct 2022 09:33:04 -0500
Organization: Aioe.org NNTP Server
Message-ID: <tijp2v$gq2$2@gioia.aioe.org>
References: <tij7cg$123$1@gioia.aioe.org> <tijil3$3esa0$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: gioia.aioe.org; logging-data="17218"; posting-host="/GRMamn3ov7sGOWkEuxPQw.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:102.0) Gecko/20100101
Thunderbird/102.3.3
X-Notice: Filtered by postfilter v. 0.9.2
Content-Language: en-US
 by: olcott - Mon, 17 Oct 2022 14:33 UTC

On 10/17/2022 7:43 AM, Mikko wrote:
> On 2022-10-17 09:30:56 +0000, Fred. Zwarts said:
>
>> I have been following the discussions about Halt deciders with
>> interest. As a retired software designer and developer, I have a lot
>> of practical experience, but not much theoretical education, although
>> the theoretical background is very interesting. I learned a lot. I
>> would like to verify that I understand it correctly. Could you point
>> out any errors in the summary below?
>>
>> 1) (Definition of halt) A program X with input Y is said to halt if it
>> reaches its end condition after a finite number of steps. It does not
>> halt if it continues to execute infinitely.
>> (So, X(Y) either halts, or it does not halt.)
>> (It is irrelevant whether the end condition is reached in the 'normal'
>> way, or by other means, e.g. an unhandled 'exception'.)
>
> Definitions vary a little among authors. Usually the halting problem and
> other computability problems define that "program" is a Turing machine.
> The exact definition of "halt" varies but often it means that the execution
> has reached a situation where there is no rule specifying what to do next.
> With other definitions one must check whether it is possible that the
> execution neither halts nor runs forever.
>
>> 2) (Definition of halt decider) A halt decider H is a program that,
>> given a program X with input Y decides, after a finite number of
>> steps, whether X(Y) halts or not.
>> (H(X,Y) itself must halt after a finite number of steps. It must
>> return either 1 if X(Y) halts, or 0 if X(Y) does not halt, where 1 and
>> 0 are a convention, which could also be two other arbitrary values.)
>
> The halt decider must be a program in the same sense as the programs it
> examines are programs. Usually the requirement is that the required halt
> decider is a Turing machine and its input is a description of a Turing
> machine.
>
>>  From 1 and 2 it follows:
>>
>> 3) If X(Y) halts, then H must return 1. If H does not return 1 in a
>> finite number of steps, it might return another interesting result,
>> but it is not a halt decider. (Not returning 1 includes returning
>> other values, not halting, or throwing 'exceptions'.)
>>
>> 4) If X(Y) does not halt, then H must return 0. If it does not return
>> 0 in a finite number of steps, it might return another interesting
>> result, but it is not a halt decider. (Not returning 0 includes
>> returning other values, not halting, or throwing 'exceptions'.)
>
> Another way to say the same is that H is not a halt decider
> if there is some X and some Y such that
> - X(Y) halts and H(X,Y) returns 0
> - X(Y) does not halt and H(X,Y) returns 1
> - H(X,Y) returns something that is neither 0 nor 1
> - H(X,Y) does not return anything
>
>> Paradoxical program:
>
> Also called "pathological program"
>
>> 5) It is always possible to construct a program P, that uses code with
>> the same logic as H, in order to do the opposite of what H(P,P) returns.
>> (P does not necessarily need to use the exact same code as H does,
>> amongst others it could use a modified copy of H, or a simulation of H.)
>>
>>  From 5 it follows that a general halt decider that works for any X
>> and Y does not exist:
>>
>>  From 3, 4 and 5 it follows:
>>
>> 6) If P(P) halts, then H should return 1, but if H would do so, P(P)
>> would not halt.
>>
>> 7) If P(P) does not halt, H should return 0, but if H would do so,
>> P(P) would halt.
>>
>> 8) If P(P) halts and H does not return 1 after a finite number of
>> steps, then H is not a halt decider.
>> (The result could nevertheless be interesting for other purposes.)
>> (It is irrelevant what causes P(P) to halt.)
>>
>> 9) If P(P) does not halt and H does not return 0 after a finite number
>> of steps, then H is not a halt decider.
>> (The result could nevertheless be interesting for other purposes.)
>
> All that is correct.
>
> Mikko
>
>

*Professor Sipser has agreed to these verbatim words* (and no more)
If simulating halt decider H correctly simulates its input D until H
correctly determines that its simulated D would never stop running
unless aborted then H can abort its simulation of D and correctly report
that D specifies a non-halting sequence of configurations.

An alternative definition for a halt decider approved by MIT Professor
Michael Sipser (author of the best selling book on the theory of
computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295
is shown above and paraphrased below:

Would D correctly simulated by H ever stop running if not aborted?
Is proven on page 3 of this paper to be "no" thus perfectly meeting the
Sipser approved criteria shown above.

*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor