Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

Long computations which yield zero are probably all for naught.


computers / comp.ai.philosophy / Concise refutation of halting problem proofs V43 [where people get stuck]

SubjectAuthor
* Concise refutation of halting problem proofs V43 [where people getolcott
`- Re: Concise refutation of halting problem proofs V43 [where peopleolcott

1
Subject: Concise refutation of halting problem proofs V43 [where people get stuck]
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, sci.logic, sci.math
Followup: comp.theory
Date: Fri, 31 Dec 2021 16:27 UTC
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!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 31 Dec 2021 10:27:27 -0600
Date: Fri, 31 Dec 2021 10:27:26 -0600
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.4.1
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic,sci.math
Content-Language: en-US
Followup-To: comp.theory
From: NoO...@NoWhere.com (olcott)
Subject: Concise refutation of halting problem proofs V43 [where people get
stuck]
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <AIednc_gnYHyslL8nZ2dnUU7-IPNnZ2d@giganews.com>
Lines: 44
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-tMyIYaKBPLBAzi78tnLsicLaODsDIqPUHMYLkqRvsRnw+cO+1/ufqGL2lRLwv5KTqT5aRu8RDM1KVfI!Zf1lrkvND+oT2wBP1SBreG5USzQjb9oN34Edg9ZfF2gEoDokjoIYlbjscozKWngYRtWUikVNCqi1!Ng==
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: 2943
View all headers
Proving that embedded_H at Ĥ.qx correctly maps its inputs ⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qn on the basis of the behavior of the UTM simulation of these inputs.

*My criterion measure with Ben's notational conventions*
H.q0 wM w ⊢* H.qy  iff UTM(wM, w) halts
H.q0 wM w ⊢* H.qn  iff UTM(wM, w) does not halt

We know that H would correctly decide the halt status of its input on the basis of correctly deciding the halt status of the UTM simulation of its input.

We know this because a UTM simulation of the Turing machine description is computationally equivalent to the direct execution of this same Turing machine.

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞  iff UTM(⟨Ĥ⟩ ⟨Ĥ⟩) at Ĥ.qx halts.
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn    iff UTM(⟨Ĥ⟩ ⟨Ĥ⟩) at Ĥ.qx does not halt.

THIS IS WHERE PEOPLE GET STUCK
THIS IS WHERE PEOPLE GET STUCK
THIS IS WHERE PEOPLE GET STUCK

The criterion measure of H applies recursively such that the UTM would simulate itself.

The following is the UTM simulation of a single input pair:
(a) copies its input ⟨Ĥ⟩ to ⟨Ĥ⟩
(b) simulates ⟨Ĥ⟩ applied to ⟨Ĥ⟩ with the UTM

We know that this means that when embedded_H computes the mapping from its input ⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qy or Ĥ.qn on the basis of the behavior of the UTM simulation of this input that its transition to Ĥ.qn is correct.

https://www.liarparadox.org/Peter_Linz_HP_315-320.pdf

Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. (315-320)

--
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 V43 [where people get stuck]
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, sci.logic, sci.math
Date: Fri, 31 Dec 2021 22:24 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 31 Dec 2021 16:24:46 -0600
Date: Fri, 31 Dec 2021 16:24:40 -0600
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.4.1
Subject: Re: Concise refutation of halting problem proofs V43 [where people
get stuck]
Content-Language: en-US
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic,sci.math
References: <AIednc_gnYHyslL8nZ2dnUU7-IPNnZ2d@giganews.com>
<sqnb4c$1nl5$1@gioia.aioe.org>
<9cidnfUHUv_grVL8nZ2dnUU7-XudnZ2d@giganews.com>
<wHGzJ.52272$bo.39043@fx18.iad>
<FIGdneWXW9MzplL8nZ2dnUU7-cfNnZ2d@giganews.com>
<oeWdnSH1X74-2VL8nZ2dnUU7-IWdnZ2d@giganews.com>
<bkIzJ.69800$xe2.62705@fx16.iad>
<pNidnReiDYTMyFL8nZ2dnUU7-VvNnZ2d@giganews.com>
<2PIzJ.95859$Gco3.18861@fx01.iad>
<eoKdnRUNgN-Aw1L8nZ2dnUU7-cvNnZ2d@giganews.com>
<weJzJ.52153$bn2.36806@fx12.iad>
<EeCdneJ1iJHf_lL8nZ2dnUU7-N3NnZ2d@giganews.com>
<83KzJ.212093$1d1.209379@fx99.iad>
<BbmdnZ-ygveK8lL8nZ2dnUU7-RfNnZ2d@giganews.com>
<MDKzJ.251382$IW4.243734@fx48.iad>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <MDKzJ.251382$IW4.243734@fx48.iad>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <Q5GdnaA9H6CzHlL8nZ2dnUU7-e3NnZ2d@giganews.com>
Lines: 112
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-V1JuZcUpCY9SgmlPpELfg6T1btVb8xQOJ+jQ3j7ZVNyTejZXa6+Qfd/RD74fN+9HVaMeirqFSo1gGgt!kYJWIPp2Szb+0eP+MOh097WHzOJb0YSYgQXfolZQsLR7WY8/u4T2JHVtCC27XQ0x2ZzQU6Lgotck!6g==
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: 6616
View all headers
On 12/31/2021 3:30 PM, Richard Damon wrote:
On 12/31/21 3:59 PM, olcott wrote:
On 12/31/2021 2:51 PM, Richard Damon wrote:
On 12/31/21 3:08 PM, olcott wrote:
On 12/31/2021 1:55 PM, Richard Damon wrote:
On 12/31/21 2:46 PM, olcott wrote:
On 12/31/2021 1:25 PM, Richard Damon wrote:
On 12/31/21 2:09 PM, olcott wrote:
On 12/31/2021 12:52 PM, Richard Damon wrote:
On 12/31/21 12:57 PM, olcott wrote:
On 12/31/2021 11:19 AM, olcott wrote:
On 12/31/2021 11:01 AM, Richard Damon wrote:
On 12/31/21 11:31 AM, olcott wrote:
On 12/31/2021 10:28 AM, Steve Parker wrote:
On 12/31/2021 8:27 AM, olcott wrote:
Proving that embedded_H at Ĥ.qx correctly maps its inputs ⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qn on the basis of the behavior of the UTM simulation of these inputs.

Shut up idiot.


If you can't point to any mistakes that proves that you are the idiot


How about that it can be simple shown by inspection that if H and embedded_H applied to <H^> <H^> goes to H.qn, then so does H^ applied to <H^> go to H^.qn and Halts, thus H was WRONG.


Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

embedded_H at Ĥ.qx is only accountable for mapping its input ⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qy or Ĥ.qn on the basis that a pure simulation of this input
(no embedded_H ever aborts the simulation of its input).

No embedded_H ever aborts the simulation of its input until:
(a) Its input halts on its own.
(b) It detects that its input would never halt on its own.


Proven impossible for such an algorithm to decide H^ is non-halting:

If is self-evidently true that unless simulating halt decider embedded_H aborts the simulation of its input at some point that Ĥ applied to ⟨Ĥ⟩ never stops running.

That you have never agreed to this proves that you are dishonest.


And YOU don't understand that no ALGORITHM can detect this.

Thus, YES, if your H that doesn't abort its simulation until IT can correctly prove the computation is non-halting, H^ will be Non-Halting and that would be the correct answer, but H can not compute that answer, and will be non-halting itself.
Well that is a breakthrough.

The correct halt status for embedded_H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ is Ĥ.qn even if embedded_H cannot compute this correct halt status.

Prior to this breakthrough both Ĥ.qy and Ĥ.qn were the wrong answer.



Right, the correct answer is Non-Halting but NEITHER H or embedded_H can give it, because if they do, it becomes the wrong answer.


When embedded_H is basing its halt status decision on the behavior pure simulation of its input then because the pure simulation of its input would never stop running when embedded_H transitions to Ĥ.qn it is necessarily correct because it is still true that the pure simulation of its input would never stop running.


So if H IS a pure simulator, the correct answer is Non-Halting, but a pure simulator will never abort itself to give that. H FAILS.


computation that halts
...the Turing machine will halt whenever it enters a final state. (Linz:1990:234)

The fact that the input to embedded_H never reaches its final state whether or not its simulation is ever aborted conclusively proves that this input never halts therefore when embedded_H transitions to Ĥ.qn it is necessarily correct.


WRONG, because the ACTUAL Turing Machine that is represented in the input WILL reach its final state,

This is why I need an actual computer scientist to review my work.

An actual computer scientist will understand that embedded_H does compute the mapping from these inputs finite strings ⟨Ĥ⟩ ⟨Ĥ⟩ to this final state Ĥ.qn on the basis that the actual input would never halt.


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