Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

The clash of ideas is the sound of freedom.


computers / comp.ai.philosophy / Re: Concise refutation of halting problem proofs V34 [ invocation invariants ]

SubjectAuthor
* Concise refutation of halting problem proofs V34 [ invocation invariants ]olcott
`* Re: Concise refutation of halting problem proofs V34 [ invocationAndré G. Isaak
 `* Re: Concise refutation of halting problem proofs V34 [ invocationolcott
  `- Re: Concise refutation of halting problem proofs V34 [ invocation invariants ]olcott

1
Concise refutation of halting problem proofs V34 [ invocation invariants ]

<6NednRcAp9L32zX8nZ2dnUU7-QHNnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory comp.ai.philosophy sci.logic sci.math
Path: i2pn2.org!i2pn.org!aioe.org!feeder1.feed.usenet.farm!feed.usenet.farm!tr3.eu1.usenetexpress.com!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Wed, 01 Dec 2021 22:07:06 -0600
Date: Wed, 1 Dec 2021 22:07:05 -0600
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Thunderbird/91.3.2
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic,sci.math
Content-Language: en-US
From: NoO...@NoWhere.com (olcott)
Subject: Concise refutation of halting problem proofs V34 [ invocation invariants ]
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <6NednRcAp9L32zX8nZ2dnUU7-QHNnZ2d@giganews.com>
Lines: 23
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-XE3MNyG4oNRVSV3WPm6XH2U+2/x/xxVwhSvuDKaxmEsl1d3FqzJSJ/wC9M/HiSmEs7U19dWZ+emMIww!Yewc1YDsKDSC41qU3Rrf+DnBRgWDrR4rQIPm1cizckZuwa+23VDjf449xDncTkk4e1R8HZkKqx9r!dA==
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 1924
 by: olcott - Thu, 2 Dec 2021 04:07 UTC

If for any number of N steps that simulating halt decider H simulates
its input (X,Y) X never reaches its final state then we know that X
never halts and H is always correct to abort the simulation of this
input and return 0.

This is the invocation invariant of the input similar to the loop
invariant and recursion invariant of proof of program correctness.

https://en.wikipedia.org/wiki/Invariant_(mathematics)

Halting problem undecidability and infinitely nested simulation V2

https://www.researchgate.net/publication/356105750_Halting_problem_undecidability_and_infinitely_nested_simulation_V2

--
Copyright 2021 Pete Olcott

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

Re: Concise refutation of halting problem proofs V34 [ invocation invariants ]

<sob248$hfe$1@dont-email.me>

 copy mid

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

 copy link   Newsgroups: comp.theory comp.ai.philosophy sci.logic sci.math
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: agis...@gm.invalid (André G. Isaak)
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic,sci.math
Subject: Re: Concise refutation of halting problem proofs V34 [ invocation
invariants ]
Date: Thu, 2 Dec 2021 11:09:05 -0700
Organization: Christians and Atheists United Against Creeping Agnosticism
Lines: 22
Message-ID: <sob248$hfe$1@dont-email.me>
References: <6NednRcAp9L32zX8nZ2dnUU7-QHNnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 2 Dec 2021 18:09:12 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="5d223ee07bf8b75dfe5a6149d468d445";
logging-data="17902"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+dsCA+YAIciWvKB6iJVOEE"
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:78.0)
Gecko/20100101 Thunderbird/78.14.0
Cancel-Lock: sha1:LCst4TZH9Z8STnVlHlQZx7EIBoA=
In-Reply-To: <6NednRcAp9L32zX8nZ2dnUU7-QHNnZ2d@giganews.com>
Content-Language: en-US
 by: André G. Isaak - Thu, 2 Dec 2021 18:09 UTC

On 2021-12-01 21:07, olcott wrote:
> If for any number of N steps that simulating halt decider H simulates
> its input (X,Y) X never reaches its final state then we know that X
> never halts and H is always correct to abort the simulation of this
> input and return 0.

What on earth is N? If that is simply a variable which can be anything
then you seem to be saying that if for 1 step the simulated input
doesn't halt then it never halts. This means pretty much every
computation whose initial state is not also a final halting state
doesn't halt according to you.

> This is the invocation invariant of the input similar to the loop
> invariant and recursion invariant of proof of program correctness.

That sentence could probably use some vinaigrette. Or syrup of ipecac.

André

--
To email remove 'invalid' & replace 'gm' with well known Google mail
service.

Re: Concise refutation of halting problem proofs V34 [ invocation invariants ]

<bd6dnRnDnpUzsTT8nZ2dnUU7-T3NnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory comp.ai.philosophy sci.logic sci.math
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 02 Dec 2021 14:29:34 -0600
Date: Thu, 2 Dec 2021 14:29:32 -0600
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.3.2
Subject: Re: Concise refutation of halting problem proofs V34 [ invocation
invariants ]
Content-Language: en-US
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic,sci.math
References: <6NednRcAp9L32zX8nZ2dnUU7-QHNnZ2d@giganews.com>
<sob248$hfe$1@dont-email.me>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <sob248$hfe$1@dont-email.me>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <bd6dnRnDnpUzsTT8nZ2dnUU7-T3NnZ2d@giganews.com>
Lines: 36
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-sx9m+g8cKEZFoZJDic9T13hpEYNYApMpskWIzXyRnb4jSlaPqczwE3CORXBbm584kStomwx64ovDvdf!UYjI3X4H6cnraYQ08CvEjOkhUK7WJxb+DlBxSk4mIrPhpbfzDhXPFpSUe3zlCE0VJHmb/CwMAZYq!dg==
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2533
 by: olcott - Thu, 2 Dec 2021 20:29 UTC

On 12/2/2021 12:09 PM, André G. Isaak wrote:
> On 2021-12-01 21:07, olcott wrote:
>> If for any number of N steps that simulating halt decider H simulates
>> its input (X,Y) X never reaches its final state then we know that X
>> never halts and H is always correct to abort the simulation of this
>> input and return 0.
>
> What on earth is N?

any arbitrary element of the set of positive integers

> If that is simply a variable which can be anything
> then you seem to be saying that if for 1 step the simulated input
> doesn't halt then it never halts. This means pretty much every
> computation whose initial state is not also a final halting state
> doesn't halt according to you.
>
>> This is the invocation invariant of the input similar to the loop
>> invariant and recursion invariant of proof of program correctness.
>
> That sentence could probably use some vinaigrette. Or syrup of ipecac.
>
> André
>

Invariants are the key element of mathematical proof of program
correctness. https://en.wikipedia.org/wiki/Invariant_(mathematics)

--
Copyright 2021 Pete Olcott

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

Re: Concise refutation of halting problem proofs V34 [ invocation invariants ]

<V4-dnQLOqp_l5DT8nZ2dnUU7-d_NnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory comp.ai.philosophy sci.logic sci.math
Followup: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!news.dns-netz.com!news.freedyn.net!newsfeed.xs4all.nl!newsfeed9.news.xs4all.nl!tr2.eu1.usenetexpress.com!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 02 Dec 2021 19:57:12 -0600
Date: Thu, 2 Dec 2021 19:57:10 -0600
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Thunderbird/91.3.2
Subject: Re: Concise refutation of halting problem proofs V34 [ invocation invariants ]
Content-Language: en-US
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic,sci.math
References: <6NednRcAp9L32zX8nZ2dnUU7-QHNnZ2d@giganews.com> <sob248$hfe$1@dont-email.me> <bd6dnRnDnpUzsTT8nZ2dnUU7-T3NnZ2d@giganews.com> <sobdk2$4cn$1@dont-email.me> <G9adnUc79tnXozT8nZ2dnUU7-WvNnZ2d@giganews.com> <sobf7s$g45$1@dont-email.me> <yNednRTmltsc2DT8nZ2dnUU7-LfNnZ2d@giganews.com> <sobiaa$43v$1@dont-email.me> <1u-dnYcxEMfb0jT8nZ2dnUU7-LvNnZ2d@giganews.com> <21dqJ.60999$hm7.35761@fx07.iad> <sobr19$qso$1@gioia.aioe.org>
From: NoO...@NoWhere.com (olcott)
Followup-To: comp.theory
In-Reply-To: <sobr19$qso$1@gioia.aioe.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <V4-dnQLOqp_l5DT8nZ2dnUU7-d_NnZ2d@giganews.com>
Lines: 150
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-7HKC+gDfClrFA4iJb8bQS6uhoKLBvxe78pig9eWXx3OjXdsx9oD29Z0VvpXTC2b3yRPMhlvYlJtK1gS!xLflldTpkI4TFRCUMHBcFoAFgh1v3asYuRfJTqqqHDoa1qDEk+/BLeF0Y9q9mUX3t53C7BbEslNW!Aw==
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 8517
 by: olcott - Fri, 3 Dec 2021 01:57 UTC

On 12/2/2021 7:14 PM, Mike Terry wrote:
> On 02/12/2021 23:54, Richard Damon wrote:
>> On 12/2/21 5:57 PM, olcott wrote:
>>> On 12/2/2021 4:45 PM, André G. Isaak wrote:
>>>> On 2021-12-02 15:15, olcott wrote:
>>>>> On 12/2/2021 3:52 PM, André G. Isaak wrote:
>>>>>> On 2021-12-02 14:44, olcott wrote:
>>>>>>> On 12/2/2021 3:25 PM, André G. Isaak wrote:
>>>>>>>> On 2021-12-02 13:29, olcott wrote:
>>>>>>>>> On 12/2/2021 12:09 PM, André G. Isaak wrote:
>>>>>>>>>> On 2021-12-01 21:07, olcott wrote:
>>>>>>>>>>> If for any number of N steps that simulating halt decider H
>>>>>>>>>>> simulates its input (X,Y) X never reaches its final state
>>>>>>>>>>> then we know that X never halts and H is always correct to
>>>>>>>>>>> abort the simulation of this input and return 0.
>>>>>>>>>>
>>>>>>>>>> What on earth is N?
>>>>>>>>>
>>>>>>>>> any arbitrary element of the set of positive integers
>>>>>>>>
>>>>>>>> And right below I explain why this leads to a nonsensical
>>>>>>>> interpretation. Of course, you ignored this.
>>>>>>>>
>>>>>>>
>>>>>>> Because there exists no N in the set of positive integers such
>>>>>>> that N steps of the simulation of the input H(X,Y) stops running
>>>>>>> we correctly conclude that (this invocation invariant proves) the
>>>>>>> input to H(X,Y) never stops running.
>>>>>>
>>>>>> So you mean 'every N' rather than 'any N'. But this just amounts
>>>>>> to saying that if X doesn't halt that it is non-halting, so why
>>>>>> bring up N at all?
>>>>>>
>>>>>
>>>>> Because my reviewers seem too dense to comprehend it any other way.
>>>>
>>>> Your "reviewers" can't understand 'every' and insist you use 'any'?
>>>>
>>>>>> But your decider, if it decides to abort its input, must do so
>>>>>> after some FINITE number of steps, so it cannot actually test for
>>>>>> 'every N'.
>>>>>
>>>>> Do you test every N in mathematical induction? (Of course not you
>>>>> dumb bunny).
>>>>
>>>> Nowhere does your 'proof' make use of anything even remotely
>>>> analogous to mathematical induction.
>>>>
>>>
>>> First, the relevant property P(n) is proven for the base case, which
>>> often corresponds to n = 0 or n = 1. Then we assume that P(n) is
>>> true, and we prove P(n+1). The proof for the base case(s) and the
>>> proof that allows us to go from P(n) to P(n+1) provide a method to
>>> prove the property for any given m >= 0 by successively proving P(0),
>>> P(1), ..., P(m). We can't actually perform the infinity of proves
>>> necessary for all choices of m >= 0, but the recipe that we provided
>>> assures us that such a proof exists for all choices of m.
>>>
>>> To reduce the possibility of error, we will structure all our
>>> induction proofs rigidly, always highlighting the following four parts:
>>>
>>> The general statement of what we want to prove;
>>> The specification of the set we will perform induction on;
>>> The statement and proof of the base case(s);
>>
>> And where is the PROOF?
>>
>>> The statement of the induction hypothesis (generally, we will assume
>>> that P(n) holds, but sometimes we need stronger assumptions, see
>>> below), the statement of P(n+1) and proof of the induction step (or
>>> case).
>>
>> And where is the PROOF?
>>
>>> https://www.cs.cornell.edu/courses/cs312/2004fa/lectures/lecture9.htm
>>
>>
>>
>>>
>>> Simulate_Steps(P,P,0)   P(P) does not reach its final state.
>>> Simulate_Steps(P,P,N)   P(P) does not reach its final state.
>>> Simulate_Steps(P,P,N+1) P(P) does not reach its final state.
>>> ∴ the input to H(P,P) never halts.
>>>
>>
>> These are just STATEMENTS, you haven't PROVED anything.
>>
>> I guess that just shows mow much you LIE.
>
> You call PO a liar quite a lot, but to be a liar PO would need to be
> deliberately trying to deceive you.  Do you think that's the case?  Or
> is it reasonable to think that PO /believes/ what he said above is a
> genuine application of the mathematical principle of induction.  [Yes,
> PO has no logical /grounds/ for thinking that, since he lacks any
> understanding of the principle, but the question is about what PO
> /believes/.]
>
> Personally, I would say PO genuinely doesn't understand that his
> arguments are idiotic, due to some psychological/neural problem.  I see
> his claims and reasoning he puts forward for them more akin to
> confabulation, where a patient invents memories and explanations for a
> state of affairs they believe to be true, without necessarily having any
> deceptive intent.
>
> Of course, there are cases where PO repeats claims (like where he
> repeats his obviously false claim to have had fully coded TMs a couple
> of years ago), even AFTER it is explained that what he is saying does
> not correspond to accepted wording of the terms used, and so is simply
> false.  Maybe it's hard to swallow that this might not be direct lying
> on PO's part, but even in these situations I suspect his
> mind/memory/understanding is so "malleable" that /to him/ it really does
> seem that he was telling the truth all the time??
>
> I don't really /know/ whether PO is conciously lying in these cases, but
> it does seem to me that PO is so thoroughly DELUDED that he could look
> at someone holding up 4 fingers and convince himself that, yes there are
> 4 fingers, but also it is correct that there are 5, or 3, for some
> reason!  (And genuinely believe that - not just be lying about it...) He
> is perhaps the ideal citizen of Oceana!  :)  Or, perhaps in his heart he
> knows he is making false claims - not easy to say either way.
>
> Perhaps a bigger point is that it doesn't really matter either way
> whether PO is actually lying or confabulating or some third option - I'm
> not even sure the distinction is meaningful in PO's case.  What he says
> is all totally irrelevant, and even if someone "proved" the PO was
> "lying" it would make no difference whatsoever to anything...
>
>
> Mike.

It is true that when-so-ever any input to simulating halt decider H(X,Y)
only stops running when its simulation has been aborted that this input
is correctly decided as not halting.

This does eliminate the conventional halting problem feedback loop
between the halt decider and its input that would otherwise make this
input undecidable to this decider.

int main() { P(P); } calls H(P,P) simulates P(P) that never halts.

Halting problem undecidability and infinitely nested simulation V2
https://www.researchgate.net/publication/356105750_Halting_problem_undecidability_and_infinitely_nested_simulation_V2

--
Copyright 2021 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