Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #26137 > unrolled thread
| Started by | Jeff Barnett <jbb@notatt.com> |
|---|---|
| First post | 2020-11-27 16:44 -0700 |
| Last post | 2020-12-05 00:41 -0700 |
| Articles | 20 on this page of 70 — 10 participants |
Back to article view | Back to comp.theory
Halting test example Jeff Barnett <jbb@notatt.com> - 2020-11-27 16:44 -0700
Re: Halting test example Jeff Barnett <jbb@notatt.com> - 2020-12-03 11:00 -0700
Re: Halting test example [ Correct refutation of Peter Linz proof ] olcott <NoOne@NoWhere.com> - 2020-12-03 12:18 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ] Jeff Barnett <jbb@notatt.com> - 2020-12-03 12:18 -0700
Re: Halting test example [ Correct refutation of Peter Linz proof ] olcott <NoOne@NoWhere.com> - 2020-12-03 13:23 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ] Jeff Barnett <jbb@notatt.com> - 2020-12-03 12:44 -0700
Re: Halting test example [ Correct refutation of Peter Linz proof ] olcott <NoOne@NoWhere.com> - 2020-12-03 13:55 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ] Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-03 20:21 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ] olcott <NoOne@NoWhere.com> - 2020-12-03 14:48 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ] Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-03 22:58 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-03 17:26 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Jeff Barnett <jbb@notatt.com> - 2020-12-03 17:21 -0700
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-03 18:31 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Jeff Barnett <jbb@notatt.com> - 2020-12-03 18:13 -0700
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-03 19:20 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-04 00:26 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-03 18:40 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-04 01:17 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-03 19:39 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Daniel Pehoushek <pehoushek1@gmail.com> - 2020-12-03 18:20 -0800
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Jeff Barnett <jbb@notatt.com> - 2020-12-03 21:23 -0700
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-04 19:49 -0800
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-04 19:31 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 13:49 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-04 21:19 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 15:43 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Richard Damon <Richard@Damon-Family.org> - 2020-12-04 17:18 -0500
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 17:07 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Richard Damon <Richard@Damon-Family.org> - 2020-12-04 18:31 -0500
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 18:05 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Richard Damon <Richard@Damon-Family.org> - 2020-12-04 19:43 -0500
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-05 01:59 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 20:38 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-05 03:55 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 22:13 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-04 20:47 -0800
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 22:55 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-04 23:26 -0800
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 09:54 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-05 16:36 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 11:04 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Andy Walker <anw@cuboid.co.uk> - 2020-12-05 16:57 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 11:16 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Andy Walker <anw@cuboid.co.uk> - 2020-12-05 17:38 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 11:46 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-05 11:50 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Andy Walker <anw@cuboid.co.uk> - 2020-12-05 13:41 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 10:42 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-12-05 05:58 -0800
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 10:55 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2020-12-05 17:08 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 11:24 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 10:35 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-05 23:36 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 17:59 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-06 02:00 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 20:17 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-06 06:06 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-05 01:13 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-04 19:58 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-12-06 01:30 +0000
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) olcott <NoOne@NoWhere.com> - 2020-12-05 19:37 -0600
Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) Richard Damon <Richard@Damon-Family.org> - 2020-12-05 21:06 -0500
Re: Halting test example [ Correct refutation of Peter Linz proof ] Jeff Barnett <jbb@notatt.com> - 2020-12-03 17:29 -0700
Re: Halting test example olcott <NoOne@NoWhere.com> - 2020-12-03 18:52 -0600
Re: Halting test example Jeff Barnett <jbb@notatt.com> - 2020-12-03 21:09 -0700
Re: Halting test example olcott <NoOne@NoWhere.com> - 2020-12-03 22:15 -0600
Re: Halting test example Jeff Barnett <jbb@notatt.com> - 2020-12-04 10:13 -0700
Re: Halting test example olcott <NoOne@NoWhere.com> - 2020-12-04 11:17 -0600
Re: Halting test example Jeff Barnett <jbb@notatt.com> - 2020-12-05 00:41 -0700
Page 2 of 4 — ← Prev page 1 [2] 3 4 Next page →
| From | Jeff Barnett <jbb@notatt.com> |
|---|---|
| Date | 2020-12-03 21:23 -0700 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <rqcdjh$hl3$1@dont-email.me> |
| In reply to | #26393 |
On 12/3/2020 7:20 PM, Daniel Pehoushek wrote: > repost for PO: > (my bet is it halts or ends in finite sized cycles. > the finite cycles may be detectable by a sat solver perhaps!) Everybody who has played with the problem knows that either 1) the conjecture is true or 2) one or both of a) the path from some finite starting point ultimately climbs without limit or b) enters a cycle with smallest integer in the cycle greater than one. The issue is 2b - you can't detect it with any test thought of to date. It's like most halting problems, you can wait and see but you have no idea when you've waited long enough. By the way, why a SAT solver? What would the variables stand for? How many would you need? Recall that the smallest counter example might be thousands of bits long: the conjecture has been checked by brute force up to astronomical values I'm told. Probabilistic graph theory doesn't seem to have made any contributions and nothing good has popped out of good old number theory. > (define haltp (function &rest arguments) > ;; Value is t if (apply function arguments) is a finite, halting > ;; computation, and nil if it isn't. > your implementation of halts that produces a proper t or nil value in > a finite amount of time.) > > (define main () > (if (haltp #checker) > (print "Conjecture crushed") > (print "Conjecture confirmed"))) > > (define checker () > ;; Loop through the positive integers looking for a counter example > ;; to the conjecture. If found, return nil. If conjecture is true, we > ;; will loop forever. Is there a clever way to tell this will happen? > (loop for n = 1 step 1 > unless (haltp #check1 n) > return nil)) > > (define check1 (n) > ;; N is an integer. We check the conjecture for n. If it's true, we > ;; return t. > (loop when (= n 1) Return t > do (if (evenp n) (setq n (/ n 2)) (setq n (+ (* 3 n) 1)))) > > Question: What does main print? There can hardly be a simpler > computation where halting or not halting is not obvious. Yet Erdos said > approximately "Mathematics is not yet ripe enough for such questions." > Your fame is ensured if you can shed some light on this example. -- Jeff Barnett
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2020-12-04 19:49 -0800 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <rqf006$18oo$1@gioia.aioe.org> |
| In reply to | #26409 |
On 12/3/2020 8:23 PM, Jeff Barnett wrote: > On 12/3/2020 7:20 PM, Daniel Pehoushek wrote: >> repost for PO: >> (my bet is it halts or ends in finite sized cycles. >> the finite cycles may be detectable by a sat solver perhaps!) > > Everybody who has played with the problem knows that either 1) the > conjecture is true or 2) one or both of a) the path from some finite > starting point ultimately climbs without limit or b) enters a cycle with > smallest integer in the cycle greater than one. The issue is 2b - you > can't detect it with any test thought of to date. It's like most halting > problems, you can wait and see but you have no idea when you've waited > long enough. [...] Exactly. A halting decider says, well, this unknown program does not halt... Its been running for 6 decades. Then, it halts on 6.5 decades. ;^)
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2020-12-04 19:31 +0000 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <20201204111142.427@kylheku.com> |
| In reply to | #26390 |
On 2020-12-04, olcott <NoOne@NoWhere.com> wrote: > On 12/3/2020 7:17 PM, Kaz Kylheku wrote: >> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote: >>> On 12/3/2020 6:26 PM, Kaz Kylheku wrote: >>>> ["Followup-To:" header set to comp.theory.] >>>> On 2020-12-03, olcott <NoOne@NoWhere.com> wrote: >>>>> The key thing is that I correctly refuted the entire Ĥ pattern. >>>> >>>> Yes, but Linz anticipates your objection to the fixed pattern. >>> >>> I do not accept that. >> >> But he acknowledges the objection. He is granting that it's right, >> with regard to that specific configuration given in the diagram! >> >> Again: >> >> Linz: "One may object to Definition 12.1, since we required that, to >> solve the halting problem, H had to start and end in very specific >> configurations." > > I don't see this. > The specific configuration is that the halt decider begins executing at > its beginning and ends with a yes or no answer. This is categorically > every possibly correct configuration. By "configuration", I'm almost certain that Linz is referring to the entire structure of his Figure 12.2, and not simply to its initial and final states. He's not using the word "configuration" in the restricted sense of "application configuration settings", which refer only to the mutable state parts. It refers to the all parts and how they fit together; the formation. He's saying: "Don't mistake the shape of that example for the technique. The example is not the technique. The intended application of the technique is the generation of an infinite variety of such structures." In other words, Linz obviously knows well that a fixed pattern for fooling a halting decider is not sufficient. He's dealing with that very objection. (He may not be doing it rigrously and with a full treatment, but he's fully covered himself against accusations of ignorance or neglect.)
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-04 13:49 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <RbednaAy34BfD1fCnZ2dnUU7-UXNnZ2d@giganews.com> |
| In reply to | #26432 |
On 12/4/2020 1:31 PM, Kaz Kylheku wrote: > On 2020-12-04, olcott <NoOne@NoWhere.com> wrote: >> On 12/3/2020 7:17 PM, Kaz Kylheku wrote: >>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote: >>>> On 12/3/2020 6:26 PM, Kaz Kylheku wrote: >>>>> ["Followup-To:" header set to comp.theory.] >>>>> On 2020-12-03, olcott <NoOne@NoWhere.com> wrote: >>>>>> The key thing is that I correctly refuted the entire Ĥ pattern. >>>>> >>>>> Yes, but Linz anticipates your objection to the fixed pattern. >>>> >>>> I do not accept that. >>> >>> But he acknowledges the objection. He is granting that it's right, >>> with regard to that specific configuration given in the diagram! >>> >>> Again: >>> >>> Linz: "One may object to Definition 12.1, since we required that, to >>> solve the halting problem, H had to start and end in very specific >>> configurations." >> >> I don't see this. >> The specific configuration is that the halt decider begins executing at >> its beginning and ends with a yes or no answer. This is categorically >> every possibly correct configuration. > > By "configuration", I'm almost certain that Linz is referring to the > entire structure of his Figure 12.2, and not simply to its initial and > final states. He's not using the word "configuration" in the restricted > sense of "application configuration settings", which refer only to the > mutable state parts. It refers to the all parts and how they fit > together; the formation. > > He's saying: "Don't mistake the shape of that example for the technique. > The example is not the technique. The intended application of the > technique is the generation of an infinite variety of such structures." > > In other words, Linz obviously knows well that a fixed pattern for > fooling a halting decider is not sufficient. He's dealing with that very > objection. (He may not be doing it rigrously and with a full treatment, > but he's fully covered himself against accusations of ignorance or > neglect.) > The same pattern of doing the opposite of whatever the halt decider decides is the same pattern of the liar paradox (if it is true that makes it untrue) and the pattern of the 1931 incompleteness theorem if you can prove that a sentence asserting its own unprovability is provable is indeed unprovable then this contradicts its assertion making it untrue. -- Copyright 2020 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2020-12-04 21:19 +0000 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <20201204130213.429@kylheku.com> |
| In reply to | #26435 |
["Followup-To:" header set to comp.theory.] On 2020-12-04, olcott <NoOne@NoWhere.com> wrote: > On 12/4/2020 1:31 PM, Kaz Kylheku wrote: >> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote: >>> On 12/3/2020 7:17 PM, Kaz Kylheku wrote: >>>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote: >>>>> On 12/3/2020 6:26 PM, Kaz Kylheku wrote: >>>>>> ["Followup-To:" header set to comp.theory.] >>>>>> On 2020-12-03, olcott <NoOne@NoWhere.com> wrote: >>>>>>> The key thing is that I correctly refuted the entire Ĥ pattern. >>>>>> >>>>>> Yes, but Linz anticipates your objection to the fixed pattern. >>>>> >>>>> I do not accept that. >>>> >>>> But he acknowledges the objection. He is granting that it's right, >>>> with regard to that specific configuration given in the diagram! >>>> >>>> Again: >>>> >>>> Linz: "One may object to Definition 12.1, since we required that, to >>>> solve the halting problem, H had to start and end in very specific >>>> configurations." >>> >>> I don't see this. >>> The specific configuration is that the halt decider begins executing at >>> its beginning and ends with a yes or no answer. This is categorically >>> every possibly correct configuration. >> >> By "configuration", I'm almost certain that Linz is referring to the >> entire structure of his Figure 12.2, and not simply to its initial and >> final states. He's not using the word "configuration" in the restricted >> sense of "application configuration settings", which refer only to the >> mutable state parts. It refers to the all parts and how they fit >> together; the formation. >> >> He's saying: "Don't mistake the shape of that example for the technique. >> The example is not the technique. The intended application of the >> technique is the generation of an infinite variety of such structures." >> >> In other words, Linz obviously knows well that a fixed pattern for >> fooling a halting decider is not sufficient. He's dealing with that very >> objection. (He may not be doing it rigrously and with a full treatment, >> but he's fully covered himself against accusations of ignorance or >> neglect.) >> > > The same pattern of doing the opposite of whatever the halt decider > decides is the same pattern of the liar paradox (if it is true that > makes it untrue) and the pattern of the 1931 incompleteness theorem if > you can prove that a sentence asserting its own unprovability is > provable is indeed unprovable then this contradicts its assertion making > it untrue. I don't see how this paragraph speaks to Linz, or your current program of showing that a static patterns is inadequate for defeating all proposed halting deciders (and thus for showing that halting is undecidable). (All the ideas you allude to can be embodied in an endless variety of concrete patterns, but that's neither here nor here.) -- TXR Programming Language: http://nongnu.org/txr Music DIY Mailing List: http://www.kylheku.com/diy ADA MP-1 Mailing List: http://www.kylheku.com/mp1
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-04 15:43 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <TZGdnRhVDt0GMFfCnZ2dnUU7-U3NnZ2d@giganews.com> |
| In reply to | #26437 |
On 12/4/2020 3:19 PM, Kaz Kylheku wrote:
> ["Followup-To:" header set to comp.theory.]
> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>> On 12/4/2020 1:31 PM, Kaz Kylheku wrote:
>>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>>>> On 12/3/2020 7:17 PM, Kaz Kylheku wrote:
>>>>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>>>>>> On 12/3/2020 6:26 PM, Kaz Kylheku wrote:
>>>>>>> ["Followup-To:" header set to comp.theory.]
>>>>>>> On 2020-12-03, olcott <NoOne@NoWhere.com> wrote:
>>>>>>>> The key thing is that I correctly refuted the entire Ĥ pattern.
>>>>>>>
>>>>>>> Yes, but Linz anticipates your objection to the fixed pattern.
>>>>>>
>>>>>> I do not accept that.
>>>>>
>>>>> But he acknowledges the objection. He is granting that it's right,
>>>>> with regard to that specific configuration given in the diagram!
>>>>>
>>>>> Again:
>>>>>
>>>>> Linz: "One may object to Definition 12.1, since we required that, to
>>>>> solve the halting problem, H had to start and end in very specific
>>>>> configurations."
>>>>
>>>> I don't see this.
>>>> The specific configuration is that the halt decider begins executing at
>>>> its beginning and ends with a yes or no answer. This is categorically
>>>> every possibly correct configuration.
>>>
>>> By "configuration", I'm almost certain that Linz is referring to the
>>> entire structure of his Figure 12.2, and not simply to its initial and
>>> final states. He's not using the word "configuration" in the restricted
>>> sense of "application configuration settings", which refer only to the
>>> mutable state parts. It refers to the all parts and how they fit
>>> together; the formation.
>>>
>>> He's saying: "Don't mistake the shape of that example for the technique.
>>> The example is not the technique. The intended application of the
>>> technique is the generation of an infinite variety of such structures."
>>>
>>> In other words, Linz obviously knows well that a fixed pattern for
>>> fooling a halting decider is not sufficient. He's dealing with that very
>>> objection. (He may not be doing it rigrously and with a full treatment,
>>> but he's fully covered himself against accusations of ignorance or
>>> neglect.)
>>>
>>
>> The same pattern of doing the opposite of whatever the halt decider
>> decides is the same pattern of the liar paradox (if it is true that
>> makes it untrue) and the pattern of the 1931 incompleteness theorem if
>> you can prove that a sentence asserting its own unprovability is
>> provable is indeed unprovable then this contradicts its assertion making
>> it untrue.
>
> I don't see how this paragraph speaks to Linz, or your current program
> of showing that a static patterns is inadequate for defeating all
> proposed halting deciders (and thus for showing that halting is
> undecidable).
(a) This sentence is not true.
(b) This sentence cannot be proven.
(c) This computation (prior to my solution)
void H_Hat(u32 P)
{
u32 Input_Halted = Halts(P, P);
if (!Input_Halted)
HALT
else
HERE: goto HERE;
}
All have the same thing in common if they are true (if Halts returns
true) that makes them false.
> (All the ideas you allude to can be embodied in an endless variety of
> concrete patterns, but that's neither here nor here.)
>
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2020-12-04 17:18 -0500 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <yAyyH.56331$NL3.12976@fx12.iad> |
| In reply to | #26435 |
On 12/4/20 2:49 PM, olcott wrote: > The same pattern of doing the opposite of whatever the halt decider > decides is the same pattern of the liar paradox (if it is true that > makes it untrue) and the pattern of the 1931 incompleteness theorem if > you can prove that a sentence asserting its own unprovability is > provable is indeed unprovable then this contradicts its assertion making > it untrue. > Actually, Linz H^ is different than the Liar's Paradox. The statement: "This Statement is False" Can not be assigned a truth value, as it is logically contradictory, In Linz, Did H^ Halt, will have a definite answer for a given decider H. The Turing Machine will difinatively either Halt or never Halt. The trick in Linz is that H can never give the right answer, that is different then there not being an answer. It is only if you somehow assert that H really does exist, do you get the Liar's Paradox.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-04 17:07 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <OsCdnSqwl_zWXFfCnZ2dnUU7-X_NnZ2d@giganews.com> |
| In reply to | #26440 |
On 12/4/2020 4:18 PM, Richard Damon wrote:
> On 12/4/20 2:49 PM, olcott wrote:
>
>> The same pattern of doing the opposite of whatever the halt decider
>> decides is the same pattern of the liar paradox (if it is true that
>> makes it untrue) and the pattern of the 1931 incompleteness theorem if
>> you can prove that a sentence asserting its own unprovability is
>> provable is indeed unprovable then this contradicts its assertion making
>> it untrue.
>>
>
> Actually, Linz H^ is different than the Liar's Paradox.
>
> The statement: "This Statement is False"
>
> Can not be assigned a truth value, as it is logically contradictory,
In this exact same way Halts cannot return a correct halting decision to
H_Hat, both {true, false} are incorrect return values to H_Hat.
void H_Hat(u32 P)
{
u32 Aborted = Halts(P, P);
if (Aborted)
HALT
else
HERE: goto HERE;
}
> In Linz, Did H^ Halt, will have a definite answer for a given decider H.
> The Turing Machine will difinatively either Halt or never Halt. The
> trick in Linz is that H can never give the right answer, that is
> different then there not being an answer. It is only if you somehow
> assert that H really does exist, do you get the Liar's Paradox.
>
Unless you apply my solution you get the Liar's paradox.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2020-12-04 18:31 -0500 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <JFzyH.42164$nc.25237@fx19.iad> |
| In reply to | #26442 |
On 12/4/20 6:07 PM, olcott wrote:
> On 12/4/2020 4:18 PM, Richard Damon wrote:
>> On 12/4/20 2:49 PM, olcott wrote:
>>
>>> The same pattern of doing the opposite of whatever the halt decider
>>> decides is the same pattern of the liar paradox (if it is true that
>>> makes it untrue) and the pattern of the 1931 incompleteness theorem if
>>> you can prove that a sentence asserting its own unprovability is
>>> provable is indeed unprovable then this contradicts its assertion making
>>> it untrue.
>>>
>>
>> Actually, Linz H^ is different than the Liar's Paradox.
>>
>> The statement: "This Statement is False"
>>
>> Can not be assigned a truth value, as it is logically contradictory,
>
> In this exact same way Halts cannot return a correct halting decision to
> H_Hat, both {true, false} are incorrect return values to H_Hat.
>
> void H_Hat(u32 P)
> {
> u32 Aborted = Halts(P, P);
> if (Aborted)
> HALT
> else
> HERE: goto HERE;
> }
>
The difference is important. The first statement has not Truth value.
The second, the question does H_Hat Halt, as a definite truth value (for
a given H), and a given H gives a definite answer, it is just that H
always give the wrong answer.
>> In Linz, Did H^ Halt, will have a definite answer for a given decider H.
>> The Turing Machine will difinatively either Halt or never Halt. The
>> trick in Linz is that H can never give the right answer, that is
>> different then there not being an answer. It is only if you somehow
>> assert that H really does exist, do you get the Liar's Paradox.
>>
>
> Unless you apply my solution you get the Liar's paradox.
>
There is a fundamental difference to a statement not having a truth
value, and a process always getting the wrong answer.
The only way you get the equivalent of the Liar's paradox is to assert
that there exists a proper machine H, if you do that, then you get the
Liar's paradox (and an inconsistant logic system).
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-04 18:05 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <ftqdndv4ZcgqU1fCnZ2dnUU7-bXNnZ2d@giganews.com> |
| In reply to | #26444 |
On 12/4/2020 5:31 PM, Richard Damon wrote:
> On 12/4/20 6:07 PM, olcott wrote:
>> On 12/4/2020 4:18 PM, Richard Damon wrote:
>>> On 12/4/20 2:49 PM, olcott wrote:
>>>
>>>> The same pattern of doing the opposite of whatever the halt decider
>>>> decides is the same pattern of the liar paradox (if it is true that
>>>> makes it untrue) and the pattern of the 1931 incompleteness theorem if
>>>> you can prove that a sentence asserting its own unprovability is
>>>> provable is indeed unprovable then this contradicts its assertion making
>>>> it untrue.
>>>>
>>>
>>> Actually, Linz H^ is different than the Liar's Paradox.
>>>
>>> The statement: "This Statement is False"
>>>
>>> Can not be assigned a truth value, as it is logically contradictory,
>>
>> In this exact same way Halts cannot return a correct halting decision to
>> H_Hat, both {true, false} are incorrect return values to H_Hat.
>>
>> void H_Hat(u32 P)
>> {
>> u32 Aborted = Halts(P, P);
>> if (Aborted)
>> HALT
>> else
>> HERE: goto HERE;
>> }
>>
>
> The difference is important. The first statement has not Truth value.
>
> The second, the question does H_Hat Halt, as a definite truth value (for
> a given H), and a given H gives a definite answer, it is just that H
> always give the wrong answer.
My H gives the right answer.
>>> In Linz, Did H^ Halt, will have a definite answer for a given decider H.
>>> The Turing Machine will difinatively either Halt or never Halt. The
>>> trick in Linz is that H can never give the right answer, that is
>>> different then there not being an answer. It is only if you somehow
>>> assert that H really does exist, do you get the Liar's Paradox.
>>>
>>
>> Unless you apply my solution you get the Liar's paradox.
>>
>
> There is a fundamental difference to a statement not having a truth
> value, and a process always getting the wrong answer.
In this case their fundamental structure is pathological self-reference,
thus identical.
> The only way you get the equivalent of the Liar's paradox is to assert
> that there exists a proper machine H, if you do that, then you get the
> Liar's paradox (and an inconsistant logic system).
>
In the exactly same way when you ask is the Liar Paradox true, the
answer is no and when you ask is the Liar Paradox false the answer is
still no, thus seeming to violate the law of the excluded middle.
In logic, the law of excluded middle (or the principle of excluded
middle) states that for any proposition, either that proposition is true
or its negation is true.
https://en.wikipedia.org/wiki/Law_of_excluded_middle
LP := ~True(LP) is not true and its negation is also not true.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2020-12-04 19:43 -0500 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <eJAyH.132703$sW6.101088@fx47.iad> |
| In reply to | #26446 |
On 12/4/20 7:05 PM, olcott wrote:
> On 12/4/2020 5:31 PM, Richard Damon wrote:
>> On 12/4/20 6:07 PM, olcott wrote:
>>> On 12/4/2020 4:18 PM, Richard Damon wrote:
>>>> On 12/4/20 2:49 PM, olcott wrote:
>>>>
>>>>> The same pattern of doing the opposite of whatever the halt decider
>>>>> decides is the same pattern of the liar paradox (if it is true that
>>>>> makes it untrue) and the pattern of the 1931 incompleteness theorem if
>>>>> you can prove that a sentence asserting its own unprovability is
>>>>> provable is indeed unprovable then this contradicts its assertion
>>>>> making
>>>>> it untrue.
>>>>>
>>>>
>>>> Actually, Linz H^ is different than the Liar's Paradox.
>>>>
>>>> The statement: "This Statement is False"
>>>>
>>>> Can not be assigned a truth value, as it is logically contradictory,
>>>
>>> In this exact same way Halts cannot return a correct halting decision to
>>> H_Hat, both {true, false} are incorrect return values to H_Hat.
>>>
>>> void H_Hat(u32 P)
>>> {
>>> u32 Aborted = Halts(P, P);
>>> if (Aborted)
>>> HALT
>>> else
>>> HERE: goto HERE;
>>> }
>>>
>>
>> The difference is important. The first statement has not Truth value.
>>
>> The second, the question does H_Hat Halt, as a definite truth value (for
>> a given H), and a given H gives a definite answer, it is just that H
>> always give the wrong answer.
>
> My H gives the right answer.
It seems not. You can not 'Define' that you have the right answer, you
need to prove it. IF you are ASSUMING or ASSERTING that the answer is
right, see blow.
>
>>>> In Linz, Did H^ Halt, will have a definite answer for a given
>>>> decider H.
>>>> The Turing Machine will difinatively either Halt or never Halt. The
>>>> trick in Linz is that H can never give the right answer, that is
>>>> different then there not being an answer. It is only if you somehow
>>>> assert that H really does exist, do you get the Liar's Paradox.
>>>>
>>>
>>> Unless you apply my solution you get the Liar's paradox.
>>>
>>
>> There is a fundamental difference to a statement not having a truth
>> value, and a process always getting the wrong answer.
>
> In this case their fundamental structure is pathological self-reference,
> thus identical.
No. The Halting of H^ given an H is to completely determined value.
THe answer of H(H^, H^) is a completely determined vslur.
The fact that they differ just says that H is incorrect, not that the
truth value is indeterminate.
Now, if you begin with an assertion that H is correct, you have created
an inconsistant system.
>
>> The only way you get the equivalent of the Liar's paradox is to assert
>> that there exists a proper machine H, if you do that, then you get the
>> Liar's paradox (and an inconsistant logic system).
>>
>
> In the exactly same way when you ask is the Liar Paradox true, the
> answer is no and when you ask is the Liar Paradox false the answer is
> still no, thus seeming to violate the law of the excluded middle.>
> In logic, the law of excluded middle (or the principle of excluded
> middle) states that for any proposition, either that proposition is true
> or its negation is true.
> https://en.wikipedia.org/wiki/Law_of_excluded_middle
>
> LP := ~True(LP) is not true and its negation is also not true.
>
And the proposistions in the halting problem are:
For a given H, does H^ Halt?
and For a given H, what does H(H^, H^) predict
These have definitive values (unless H is so bad it actually fails to
decide), so things are different than the Liar's paradox.
The Assertion that H is correct, will create the Liar's paradox, but
that is not the question of the halting problem.
The question of the Halting problem is can an H be defined that answers
for all machines/inputs, and that answer is show to be no, as to assert
that it is, would be to create the Liar's Paradox and require its truth
to be determined.
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2020-12-05 01:59 +0000 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <20201204174902.184@kylheku.com> |
| In reply to | #26442 |
On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
> On 12/4/2020 4:18 PM, Richard Damon wrote:
>> On 12/4/20 2:49 PM, olcott wrote:
>>
>>> The same pattern of doing the opposite of whatever the halt decider
>>> decides is the same pattern of the liar paradox (if it is true that
>>> makes it untrue) and the pattern of the 1931 incompleteness theorem if
>>> you can prove that a sentence asserting its own unprovability is
>>> provable is indeed unprovable then this contradicts its assertion making
>>> it untrue.
>>>
>>
>> Actually, Linz H^ is different than the Liar's Paradox.
>>
>> The statement: "This Statement is False"
>>
>> Can not be assigned a truth value, as it is logically contradictory,
>
> In this exact same way Halts cannot return a correct halting decision to
> H_Hat, both {true, false} are incorrect return values to H_Hat.
- The Liar Paradox *does not* have a valid interpretation of its truth
value.
That's a statement about reality.
- Halts *cannot* return a correct value, sure
That's a statement about a fantasy: the wish to have it return a correct
value, which doesn't come true.
Halts in fact *does* return a specific, and that value is wrong.
There is no paradox.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-04 20:38 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <hd6dnYblCoAKb1fCnZ2dnUU7-KnNnZ2d@giganews.com> |
| In reply to | #26455 |
On 12/4/2020 7:59 PM, Kaz Kylheku wrote:
> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>> On 12/4/2020 4:18 PM, Richard Damon wrote:
>>> On 12/4/20 2:49 PM, olcott wrote:
>>>
>>>> The same pattern of doing the opposite of whatever the halt decider
>>>> decides is the same pattern of the liar paradox (if it is true that
>>>> makes it untrue) and the pattern of the 1931 incompleteness theorem if
>>>> you can prove that a sentence asserting its own unprovability is
>>>> provable is indeed unprovable then this contradicts its assertion making
>>>> it untrue.
>>>>
>>>
>>> Actually, Linz H^ is different than the Liar's Paradox.
>>>
>>> The statement: "This Statement is False"
>>>
>>> Can not be assigned a truth value, as it is logically contradictory,
>>
>> In this exact same way Halts cannot return a correct halting decision to
>> H_Hat, both {true, false} are incorrect return values to H_Hat.
>
> - The Liar Paradox *does not* have a valid interpretation of its truth
> value.
>
> That's a statement about reality.
>
> - Halts *cannot* return a correct value, sure
>
> That's a statement about a fantasy: the wish to have it return a correct
> value, which doesn't come true.
>
> Halts in fact *does* return a specific, and that value is wrong.
>
> There is no paradox.
>
Actual debug trace of H() correctly deciding halting on H_Hat()
void H_Hat(u32 P)
{
u32 Input_Halts = H(P, P);
if (Input_Halts)
HERE: goto HERE;
else
HALT
}
int main()
{
H((u32)H_Hat, (u32)H_Hat);
HALT;
}
_H_Hat()
[000005e0](01) 55 push ebp
[000005e1](02) 8bec mov ebp,esp
[000005e3](01) 51 push ecx
[000005e4](03) 8b4508 mov eax,[ebp+08]
[000005e7](01) 50 push eax
[000005e8](03) 8b4d08 mov ecx,[ebp+08]
[000005eb](01) 51 push ecx
[000005ec](05) e87ffdffff call 00000370
[000005f1](03) 83c408 add esp,+08
[000005f4](03) 8945fc mov [ebp-04],eax
[000005f7](04) 837dfc00 cmp dword [ebp-04],+00
[000005fb](02) 7404 jz 00000601
[000005fd](02) ebfe jmp 000005fd
[000005ff](02) eb01 jmp 00000602
[00000601](01) f4 hlt
[00000602](02) 8be5 mov esp,ebp
[00000604](01) 5d pop ebp
[00000605](01) c3 ret
_main()
[00000610](01) 55 push ebp
[00000611](02) 8bec mov ebp,esp
[00000613](05) 68e0050000 push 000005e0
[00000618](05) 68e0050000 push 000005e0
[0000061d](05) e84efdffff call 00000370
[00000622](03) 83c408 add esp,+08
[00000625](01) f4 hlt
[00000626](01) 5d pop ebp
[00000627](01) c3 ret
Output_Debug_Trace() Trace_List.size(20)
[00000610](01) EMU_Level(0) 55 push ebp
[00000611](02) EMU_Level(0) 8bec mov ebp,esp
[00000613](05) EMU_Level(0) 68e0050000 push 000005e0
[00000618](05) EMU_Level(0) 68e0050000 push 000005e0
[0000061d](05) EMU_Level(0) e84efdffff call 00000370
----CALL [00000370]
[000005e0](01) EMU_Level(1) 55 push ebp
[000005e1](02) EMU_Level(1) 8bec mov ebp,esp
[000005e3](01) EMU_Level(1) 51 push ecx
[000005e4](03) EMU_Level(1) 8b4508 mov eax,[ebp+08]
[000005e7](01) EMU_Level(1) 50 push eax
[000005e8](03) EMU_Level(1) 8b4d08 mov ecx,[ebp+08]
[000005eb](01) EMU_Level(1) 51 push ecx
[000005ec](05) EMU_Level(1) e87ffdffff call 00000370
----CALL [00000370]
[000005e0](01) EMU_Level(2) 55 push ebp
[000005e1](02) EMU_Level(2) 8bec mov ebp,esp
[000005e3](01) EMU_Level(2) 51 push ecx
[000005e4](03) EMU_Level(2) 8b4508 mov eax,[ebp+08]
[000005e7](01) EMU_Level(2) 50 push eax
[000005e8](03) EMU_Level(2) 8b4d08 mov ecx,[ebp+08]
[000005eb](01) EMU_Level(2) 51 push ecx
[000005ec](05) EMU_Level(2) e87ffdffff call 00000370
----CALL [00000370]
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
Number of Instructions Executed(2777)
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2020-12-05 03:55 +0000 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <20201204195042.869@kylheku.com> |
| In reply to | #26459 |
["Followup-To:" header set to comp.theory.]
On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
> On 12/4/2020 7:59 PM, Kaz Kylheku wrote:
>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>>> On 12/4/2020 4:18 PM, Richard Damon wrote:
>>>> On 12/4/20 2:49 PM, olcott wrote:
>>>>
>>>>> The same pattern of doing the opposite of whatever the halt decider
>>>>> decides is the same pattern of the liar paradox (if it is true that
>>>>> makes it untrue) and the pattern of the 1931 incompleteness theorem if
>>>>> you can prove that a sentence asserting its own unprovability is
>>>>> provable is indeed unprovable then this contradicts its assertion making
>>>>> it untrue.
>>>>>
>>>>
>>>> Actually, Linz H^ is different than the Liar's Paradox.
>>>>
>>>> The statement: "This Statement is False"
>>>>
>>>> Can not be assigned a truth value, as it is logically contradictory,
>>>
>>> In this exact same way Halts cannot return a correct halting decision to
>>> H_Hat, both {true, false} are incorrect return values to H_Hat.
>>
>> - The Liar Paradox *does not* have a valid interpretation of its truth
>> value.
>>
>> That's a statement about reality.
>>
>> - Halts *cannot* return a correct value, sure
>>
>> That's a statement about a fantasy: the wish to have it return a correct
>> value, which doesn't come true.
>>
>> Halts in fact *does* return a specific, and that value is wrong.
>>
>> There is no paradox.
>>
>
> Actual debug trace of H() correctly deciding halting on H_Hat()
>
>
> void H_Hat(u32 P)
> {
> u32 Input_Halts = H(P, P);
> if (Input_Halts)
> HERE: goto HERE;
> else
> HALT
> }
>
>
> int main()
> {
> H((u32)H_Hat, (u32)H_Hat);
> HALT;
> }
>
> The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
> Number of Instructions Executed(2777)
Here, H_Hat has not terminated. Yet, H has not returned the correct
value to indicate this. The whole show simply stopped.
Therefore H did not decide anything.
H must terminate by returning normally with a return value that
is true or false.
You need a program like this:
int main()
{
if (H((u32)H_Hat, (u32)H_Hat)) {
puts("H_Hat(H_Hat) halts!");
} else {
puts("H_Hat(H_Hat) does not hal!");
}
return 0;
}
This program must terminate, having printed either one of the two
messages. If it does so, then it is deemed to have successfully decided.
If it fails to terminate, then it has not decided.
If it crashes for any reason (division by zero, segmenation fault,
or "Instruction Specifies Infinite Recursion", then it has not decided.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-04 22:13 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <4rydnZ7uPrNplVbCnZ2dnUU7-aXNnZ2d@giganews.com> |
| In reply to | #26464 |
On 12/4/2020 9:55 PM, Kaz Kylheku wrote:
> ["Followup-To:" header set to comp.theory.]
> On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
>> On 12/4/2020 7:59 PM, Kaz Kylheku wrote:
>>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>>>> On 12/4/2020 4:18 PM, Richard Damon wrote:
>>>>> On 12/4/20 2:49 PM, olcott wrote:
>>>>>
>>>>>> The same pattern of doing the opposite of whatever the halt decider
>>>>>> decides is the same pattern of the liar paradox (if it is true that
>>>>>> makes it untrue) and the pattern of the 1931 incompleteness theorem if
>>>>>> you can prove that a sentence asserting its own unprovability is
>>>>>> provable is indeed unprovable then this contradicts its assertion making
>>>>>> it untrue.
>>>>>>
>>>>>
>>>>> Actually, Linz H^ is different than the Liar's Paradox.
>>>>>
>>>>> The statement: "This Statement is False"
>>>>>
>>>>> Can not be assigned a truth value, as it is logically contradictory,
>>>>
>>>> In this exact same way Halts cannot return a correct halting decision to
>>>> H_Hat, both {true, false} are incorrect return values to H_Hat.
>>>
>>> - The Liar Paradox *does not* have a valid interpretation of its truth
>>> value.
>>>
>>> That's a statement about reality.
>>>
>>> - Halts *cannot* return a correct value, sure
>>>
>>> That's a statement about a fantasy: the wish to have it return a correct
>>> value, which doesn't come true.
>>>
>>> Halts in fact *does* return a specific, and that value is wrong.
>>>
>>> There is no paradox.
>>>
>>
>> Actual debug trace of H() correctly deciding halting on H_Hat()
>>
>>
>> void H_Hat(u32 P)
>> {
>> u32 Input_Halts = H(P, P);
>> if (Input_Halts)
>> HERE: goto HERE;
>> else
>> HALT
>> }
>>
>>
>> int main()
>> {
>> H((u32)H_Hat, (u32)H_Hat);
>> HALT;
>> }
>>
>> The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
>> Number of Instructions Executed(2777)
>
> Here, H_Hat has not terminated. Yet, H has not returned the correct
> value to indicate this. The whole show simply stopped.
>
> Therefore H did not decide anything.
>
> H must terminate by returning normally with a return value that
> is true or false.
>
> You need a program like this:
>
> int main()
> {
> if (H((u32)H_Hat, (u32)H_Hat)) {
> puts("H_Hat(H_Hat) halts!");
> } else {
> puts("H_Hat(H_Hat) does not hal!");
> }
>
> return 0;
> }
>
> This program must terminate, having printed either one of the two
> messages. If it does so, then it is deemed to have successfully decided.
I am working on this. This is actually just window dressing.
It is a little tricky unwinding recursion cleanly.
My execution trace already proved that Halts(H_Hat, H_Hat) is decidable.
I wonder if Ben will ever acknowledge that I did what I said that I would.
Basically I am just biding my time here until I complete the enhancement
that you suggest. I have been working on this for a few days now. x86utm
is a multi-tasking operating system and I captured the data that I need
for the context switch to provide the above result. I haven't got this
working yet.
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2020-12-04 20:47 -0800 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <rqf3dg$9n3$1@gioia.aioe.org> |
| In reply to | #26467 |
On 12/4/2020 8:13 PM, olcott wrote:
> On 12/4/2020 9:55 PM, Kaz Kylheku wrote:
>> ["Followup-To:" header set to comp.theory.]
>> On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
>>> On 12/4/2020 7:59 PM, Kaz Kylheku wrote:
>>>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>>>>> On 12/4/2020 4:18 PM, Richard Damon wrote:
>>>>>> On 12/4/20 2:49 PM, olcott wrote:
>>>>>>
>>>>>>> The same pattern of doing the opposite of whatever the halt decider
>>>>>>> decides is the same pattern of the liar paradox (if it is true that
>>>>>>> makes it untrue) and the pattern of the 1931 incompleteness
>>>>>>> theorem if
>>>>>>> you can prove that a sentence asserting its own unprovability is
>>>>>>> provable is indeed unprovable then this contradicts its assertion
>>>>>>> making
>>>>>>> it untrue.
>>>>>>>
>>>>>>
>>>>>> Actually, Linz H^ is different than the Liar's Paradox.
>>>>>>
>>>>>> The statement: "This Statement is False"
>>>>>>
>>>>>> Can not be assigned a truth value, as it is logically contradictory,
>>>>>
>>>>> In this exact same way Halts cannot return a correct halting
>>>>> decision to
>>>>> H_Hat, both {true, false} are incorrect return values to H_Hat.
>>>>
>>>> - The Liar Paradox *does not* have a valid interpretation of its truth
>>>> value.
>>>>
>>>> That's a statement about reality.
>>>>
>>>> - Halts *cannot* return a correct value, sure
>>>>
>>>> That's a statement about a fantasy: the wish to have it return a
>>>> correct
>>>> value, which doesn't come true.
>>>>
>>>> Halts in fact *does* return a specific, and that value is wrong.
>>>>
>>>> There is no paradox.
>>>>
>>>
>>> Actual debug trace of H() correctly deciding halting on H_Hat()
>>>
>>>
>>> void H_Hat(u32 P)
>>> {
>>> u32 Input_Halts = H(P, P);
>>> if (Input_Halts)
>>> HERE: goto HERE;
>>> else
>>> HALT
>>> }
>>>
>>>
>>> int main()
>>> {
>>> H((u32)H_Hat, (u32)H_Hat);
>>> HALT;
>>> }
>>>
>>> The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
>>> Number of Instructions Executed(2777)
>>
>> Here, H_Hat has not terminated. Yet, H has not returned the correct
>> value to indicate this. The whole show simply stopped.
>>
>> Therefore H did not decide anything.
>>
>> H must terminate by returning normally with a return value that
>> is true or false.
>>
>> You need a program like this:
>>
>> int main()
>> {
>> if (H((u32)H_Hat, (u32)H_Hat)) {
>> puts("H_Hat(H_Hat) halts!");
>> } else {
>> puts("H_Hat(H_Hat) does not hal!");
>> }
>>
>> return 0;
>> }
>>
>> This program must terminate, having printed either one of the two
>> messages. If it does so, then it is deemed to have successfully decided.
>
> I am working on this. This is actually just window dressing.
> It is a little tricky unwinding recursion cleanly.
[...]
Has your window been splashed with black paint? Can it tell if an
unknown function halts? I say, hell no.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-04 22:55 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <UeydnZ6NPuJej1bCnZ2dnUU7-KWdnZ2d@giganews.com> |
| In reply to | #26468 |
On 12/4/2020 10:47 PM, Chris M. Thomasson wrote:
> On 12/4/2020 8:13 PM, olcott wrote:
>> On 12/4/2020 9:55 PM, Kaz Kylheku wrote:
>>> ["Followup-To:" header set to comp.theory.]
>>> On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
>>>> On 12/4/2020 7:59 PM, Kaz Kylheku wrote:
>>>>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>>>>>> On 12/4/2020 4:18 PM, Richard Damon wrote:
>>>>>>> On 12/4/20 2:49 PM, olcott wrote:
>>>>>>>
>>>>>>>> The same pattern of doing the opposite of whatever the halt decider
>>>>>>>> decides is the same pattern of the liar paradox (if it is true that
>>>>>>>> makes it untrue) and the pattern of the 1931 incompleteness
>>>>>>>> theorem if
>>>>>>>> you can prove that a sentence asserting its own unprovability is
>>>>>>>> provable is indeed unprovable then this contradicts its
>>>>>>>> assertion making
>>>>>>>> it untrue.
>>>>>>>>
>>>>>>>
>>>>>>> Actually, Linz H^ is different than the Liar's Paradox.
>>>>>>>
>>>>>>> The statement: "This Statement is False"
>>>>>>>
>>>>>>> Can not be assigned a truth value, as it is logically contradictory,
>>>>>>
>>>>>> In this exact same way Halts cannot return a correct halting
>>>>>> decision to
>>>>>> H_Hat, both {true, false} are incorrect return values to H_Hat.
>>>>>
>>>>> - The Liar Paradox *does not* have a valid interpretation of its truth
>>>>> value.
>>>>>
>>>>> That's a statement about reality.
>>>>>
>>>>> - Halts *cannot* return a correct value, sure
>>>>>
>>>>> That's a statement about a fantasy: the wish to have it return
>>>>> a correct
>>>>> value, which doesn't come true.
>>>>>
>>>>> Halts in fact *does* return a specific, and that value is wrong.
>>>>>
>>>>> There is no paradox.
>>>>>
>>>>
>>>> Actual debug trace of H() correctly deciding halting on H_Hat()
>>>>
>>>>
>>>> void H_Hat(u32 P)
>>>> {
>>>> u32 Input_Halts = H(P, P);
>>>> if (Input_Halts)
>>>> HERE: goto HERE;
>>>> else
>>>> HALT
>>>> }
>>>>
>>>>
>>>> int main()
>>>> {
>>>> H((u32)H_Hat, (u32)H_Hat);
>>>> HALT;
>>>> }
>>>>
>>>> The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
>>>> Number of Instructions Executed(2777)
>>>
>>> Here, H_Hat has not terminated. Yet, H has not returned the correct
>>> value to indicate this. The whole show simply stopped.
>>>
>>> Therefore H did not decide anything.
>>>
>>> H must terminate by returning normally with a return value that
>>> is true or false.
>>>
>>> You need a program like this:
>>>
>>> int main()
>>> {
>>> if (H((u32)H_Hat, (u32)H_Hat)) {
>>> puts("H_Hat(H_Hat) halts!");
>>> } else {
>>> puts("H_Hat(H_Hat) does not hal!");
>>> }
>>>
>>> return 0;
>>> }
>>>
>>> This program must terminate, having printed either one of the two
>>> messages. If it does so, then it is deemed to have successfully decided.
>>
>> I am working on this. This is actually just window dressing.
>> It is a little tricky unwinding recursion cleanly.
> [...]
>
> Has your window been splashed with black paint? Can it tell if an
> unknown function halts? I say, hell no.
>
It can correctly tell if the impossible to decide function halts.
see page 319:
http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2020-12-04 23:26 -0800 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <rqfcnf$16a0$2@gioia.aioe.org> |
| In reply to | #26470 |
On 12/4/2020 8:55 PM, olcott wrote:
> On 12/4/2020 10:47 PM, Chris M. Thomasson wrote:
>> On 12/4/2020 8:13 PM, olcott wrote:
>>> On 12/4/2020 9:55 PM, Kaz Kylheku wrote:
>>>> ["Followup-To:" header set to comp.theory.]
>>>> On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
>>>>> On 12/4/2020 7:59 PM, Kaz Kylheku wrote:
>>>>>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>>>>>>> On 12/4/2020 4:18 PM, Richard Damon wrote:
>>>>>>>> On 12/4/20 2:49 PM, olcott wrote:
>>>>>>>>
>>>>>>>>> The same pattern of doing the opposite of whatever the halt
>>>>>>>>> decider
>>>>>>>>> decides is the same pattern of the liar paradox (if it is true
>>>>>>>>> that
>>>>>>>>> makes it untrue) and the pattern of the 1931 incompleteness
>>>>>>>>> theorem if
>>>>>>>>> you can prove that a sentence asserting its own unprovability is
>>>>>>>>> provable is indeed unprovable then this contradicts its
>>>>>>>>> assertion making
>>>>>>>>> it untrue.
>>>>>>>>>
>>>>>>>>
>>>>>>>> Actually, Linz H^ is different than the Liar's Paradox.
>>>>>>>>
>>>>>>>> The statement: "This Statement is False"
>>>>>>>>
>>>>>>>> Can not be assigned a truth value, as it is logically
>>>>>>>> contradictory,
>>>>>>>
>>>>>>> In this exact same way Halts cannot return a correct halting
>>>>>>> decision to
>>>>>>> H_Hat, both {true, false} are incorrect return values to H_Hat.
>>>>>>
>>>>>> - The Liar Paradox *does not* have a valid interpretation of its
>>>>>> truth
>>>>>> value.
>>>>>>
>>>>>> That's a statement about reality.
>>>>>>
>>>>>> - Halts *cannot* return a correct value, sure
>>>>>>
>>>>>> That's a statement about a fantasy: the wish to have it return
>>>>>> a correct
>>>>>> value, which doesn't come true.
>>>>>>
>>>>>> Halts in fact *does* return a specific, and that value is wrong.
>>>>>>
>>>>>> There is no paradox.
>>>>>>
>>>>>
>>>>> Actual debug trace of H() correctly deciding halting on H_Hat()
>>>>>
>>>>>
>>>>> void H_Hat(u32 P)
>>>>> {
>>>>> u32 Input_Halts = H(P, P);
>>>>> if (Input_Halts)
>>>>> HERE: goto HERE;
>>>>> else
>>>>> HALT
>>>>> }
>>>>>
>>>>>
>>>>> int main()
>>>>> {
>>>>> H((u32)H_Hat, (u32)H_Hat);
>>>>> HALT;
>>>>> }
>>>>>
>>>>> The PRIOR Instruction Specifies Infinite Recursion: Simulation
>>>>> Stopped:
>>>>> Number of Instructions Executed(2777)
>>>>
>>>> Here, H_Hat has not terminated. Yet, H has not returned the correct
>>>> value to indicate this. The whole show simply stopped.
>>>>
>>>> Therefore H did not decide anything.
>>>>
>>>> H must terminate by returning normally with a return value that
>>>> is true or false.
>>>>
>>>> You need a program like this:
>>>>
>>>> int main()
>>>> {
>>>> if (H((u32)H_Hat, (u32)H_Hat)) {
>>>> puts("H_Hat(H_Hat) halts!");
>>>> } else {
>>>> puts("H_Hat(H_Hat) does not hal!");
>>>> }
>>>>
>>>> return 0;
>>>> }
>>>>
>>>> This program must terminate, having printed either one of the two
>>>> messages. If it does so, then it is deemed to have successfully
>>>> decided.
>>>
>>> I am working on this. This is actually just window dressing.
>>> It is a little tricky unwinding recursion cleanly.
>> [...]
>>
>> Has your window been splashed with black paint? Can it tell if an
>> unknown function halts? I say, hell no.
>>
>
> It can correctly tell if the impossible to decide function halts.
> see page 319:
> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>
When does this halt?
<pseudo-code>
______________________________
void test_program()
{
unsigned long n = 666666666;
for (unsigned long x = 0; x < n; ++x)
{
double random_number = roll(); // from 0...1
if (random_number < .5)
{
x = 0;
}
}
}
______________________________
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2020-12-05 09:54 -0600 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <GpWdnYvC1LasMFbCnZ2dnUU7-b_NnZ2d@giganews.com> |
| In reply to | #26471 |
On 12/5/2020 1:26 AM, Chris M. Thomasson wrote:
> On 12/4/2020 8:55 PM, olcott wrote:
>> On 12/4/2020 10:47 PM, Chris M. Thomasson wrote:
>>> On 12/4/2020 8:13 PM, olcott wrote:
>>>> On 12/4/2020 9:55 PM, Kaz Kylheku wrote:
>>>>> ["Followup-To:" header set to comp.theory.]
>>>>> On 2020-12-05, olcott <NoOne@NoWhere.com> wrote:
>>>>>> On 12/4/2020 7:59 PM, Kaz Kylheku wrote:
>>>>>>> On 2020-12-04, olcott <NoOne@NoWhere.com> wrote:
>>>>>>>> On 12/4/2020 4:18 PM, Richard Damon wrote:
>>>>>>>>> On 12/4/20 2:49 PM, olcott wrote:
>>>>>>>>>
>>>>>>>>>> The same pattern of doing the opposite of whatever the halt
>>>>>>>>>> decider
>>>>>>>>>> decides is the same pattern of the liar paradox (if it is true
>>>>>>>>>> that
>>>>>>>>>> makes it untrue) and the pattern of the 1931 incompleteness
>>>>>>>>>> theorem if
>>>>>>>>>> you can prove that a sentence asserting its own unprovability is
>>>>>>>>>> provable is indeed unprovable then this contradicts its
>>>>>>>>>> assertion making
>>>>>>>>>> it untrue.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Actually, Linz H^ is different than the Liar's Paradox.
>>>>>>>>>
>>>>>>>>> The statement: "This Statement is False"
>>>>>>>>>
>>>>>>>>> Can not be assigned a truth value, as it is logically
>>>>>>>>> contradictory,
>>>>>>>>
>>>>>>>> In this exact same way Halts cannot return a correct halting
>>>>>>>> decision to
>>>>>>>> H_Hat, both {true, false} are incorrect return values to H_Hat.
>>>>>>>
>>>>>>> - The Liar Paradox *does not* have a valid interpretation of its
>>>>>>> truth
>>>>>>> value.
>>>>>>>
>>>>>>> That's a statement about reality.
>>>>>>>
>>>>>>> - Halts *cannot* return a correct value, sure
>>>>>>>
>>>>>>> That's a statement about a fantasy: the wish to have it
>>>>>>> return a correct
>>>>>>> value, which doesn't come true.
>>>>>>>
>>>>>>> Halts in fact *does* return a specific, and that value is wrong.
>>>>>>>
>>>>>>> There is no paradox.
>>>>>>>
>>>>>>
>>>>>> Actual debug trace of H() correctly deciding halting on H_Hat()
>>>>>>
>>>>>>
>>>>>> void H_Hat(u32 P)
>>>>>> {
>>>>>> u32 Input_Halts = H(P, P);
>>>>>> if (Input_Halts)
>>>>>> HERE: goto HERE;
>>>>>> else
>>>>>> HALT
>>>>>> }
>>>>>>
>>>>>>
>>>>>> int main()
>>>>>> {
>>>>>> H((u32)H_Hat, (u32)H_Hat);
>>>>>> HALT;
>>>>>> }
>>>>>>
>>>>>> The PRIOR Instruction Specifies Infinite Recursion: Simulation
>>>>>> Stopped:
>>>>>> Number of Instructions Executed(2777)
>>>>>
>>>>> Here, H_Hat has not terminated. Yet, H has not returned the correct
>>>>> value to indicate this. The whole show simply stopped.
>>>>>
>>>>> Therefore H did not decide anything.
>>>>>
>>>>> H must terminate by returning normally with a return value that
>>>>> is true or false.
>>>>>
>>>>> You need a program like this:
>>>>>
>>>>> int main()
>>>>> {
>>>>> if (H((u32)H_Hat, (u32)H_Hat)) {
>>>>> puts("H_Hat(H_Hat) halts!");
>>>>> } else {
>>>>> puts("H_Hat(H_Hat) does not hal!");
>>>>> }
>>>>>
>>>>> return 0;
>>>>> }
>>>>>
>>>>> This program must terminate, having printed either one of the two
>>>>> messages. If it does so, then it is deemed to have successfully
>>>>> decided.
>>>>
>>>> I am working on this. This is actually just window dressing.
>>>> It is a little tricky unwinding recursion cleanly.
>>> [...]
>>>
>>> Has your window been splashed with black paint? Can it tell if an
>>> unknown function halts? I say, hell no.
>>>
>>
>> It can correctly tell if the impossible to decide function halts.
>> see page 319:
>> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>>
>
I have refuted the halting problem proofs by correctly deciding the
"provably" impossible to decide input.
Deciding halting on your example is probably not provably impossible.
Once everyone agrees that I have correctly decided the provable
impossible to decide input, then I will begin to look at other examples
such as yours.
> When does this halt?
>
> <pseudo-code>
> ______________________________
> void test_program()
> {
> unsigned long n = 666666666;
>
> for (unsigned long x = 0; x < n; ++x)
> {
> double random_number = roll(); // from 0...1
>
> if (random_number < .5)
> {
> x = 0;
> }
> }
> }
> ______________________________
>
--
Copyright 2020 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2020-12-05 16:36 +0000 |
| Subject | Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz) |
| Message-ID | <20201205083241.121@kylheku.com> |
| In reply to | #26479 |
On 2020-12-05, olcott <NoOne@NoWhere.com> wrote: > I have refuted the halting problem proofs by correctly deciding the > "provably" impossible to decide input. > > Deciding halting on your example is probably not provably impossible. Sure ... all we need is that definition of H() (the simple H() which isn't trying to solve the general problem at all) yet which decides correctly when embedded in that supposedly decidable case. -- TXR Programming Language: http://nongnu.org/txr
[toc] | [prev] | [next] | [standalone]
Page 2 of 4 — ← Prev page 1 [2] 3 4 Next page →
Back to top | Article view | comp.theory
csiph-web