Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

Function reject.


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

SubjectAuthor
* Concise refutation of halting problem proofs V34 [ invocation invarianolcott
`* 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 invarianolcott

1
Subject: Concise refutation of halting problem proofs V34 [ invocation invariants ]
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, sci.logic, sci.math
Date: Thu, 2 Dec 2021 04:07 UTC
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
View all headers
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


Subject: Re: Concise refutation of halting problem proofs V34 [ invocation invariants ]
From: André G. Isaak
Newsgroups: comp.theory, comp.ai.philosophy, sci.logic, sci.math
Organization: Christians and Atheists United Against Creeping Agnosticism
Date: Thu, 2 Dec 2021 18:09 UTC
References: 1
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
View all headers
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.


Subject: Re: Concise refutation of halting problem proofs V34 [ invocation invariants ]
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, sci.logic, sci.math
Date: Thu, 2 Dec 2021 20:29 UTC
References: 1 2
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
View all headers
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


Subject: Re: Concise refutation of halting problem proofs V34 [ invocation invariants ]
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, sci.logic, sci.math
Followup: comp.theory
Date: Fri, 3 Dec 2021 01:57 UTC
References: 1 2 3 4 5 6 7 8 9 10 11
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
View all headers
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
rocksolid light 0.7.2
clearneti2ptor