Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #26137 > unrolled thread

Halting test example

Started byJeff Barnett <jbb@notatt.com>
First post2020-11-27 16:44 -0700
Last post2020-12-05 00:41 -0700
Articles 20 on this page of 70 — 10 participants

Back to article view | Back to comp.theory


Contents

  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 →


#26409 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

FromJeff Barnett <jbb@notatt.com>
Date2020-12-03 21:23 -0700
SubjectRe: 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]


#26463 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2020-12-04 19:49 -0800
SubjectRe: 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]


#26432 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2020-12-04 19:31 +0000
SubjectRe: 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]


#26435 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

Fromolcott <NoOne@NoWhere.com>
Date2020-12-04 13:49 -0600
SubjectRe: 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]


#26437 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2020-12-04 21:19 +0000
SubjectRe: 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]


#26438 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

Fromolcott <NoOne@NoWhere.com>
Date2020-12-04 15:43 -0600
SubjectRe: 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]


#26440 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

FromRichard Damon <Richard@Damon-Family.org>
Date2020-12-04 17:18 -0500
SubjectRe: 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]


#26442 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

Fromolcott <NoOne@NoWhere.com>
Date2020-12-04 17:07 -0600
SubjectRe: 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]


#26444 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

FromRichard Damon <Richard@Damon-Family.org>
Date2020-12-04 18:31 -0500
SubjectRe: 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]


#26446 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

Fromolcott <NoOne@NoWhere.com>
Date2020-12-04 18:05 -0600
SubjectRe: 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]


#26448 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

FromRichard Damon <Richard@Damon-Family.org>
Date2020-12-04 19:43 -0500
SubjectRe: 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]


#26455 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2020-12-05 01:59 +0000
SubjectRe: 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]


#26459 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

Fromolcott <NoOne@NoWhere.com>
Date2020-12-04 20:38 -0600
SubjectRe: 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]


#26464 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2020-12-05 03:55 +0000
SubjectRe: 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]


#26467 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

Fromolcott <NoOne@NoWhere.com>
Date2020-12-04 22:13 -0600
SubjectRe: 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]


#26468 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2020-12-04 20:47 -0800
SubjectRe: 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]


#26470 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

Fromolcott <NoOne@NoWhere.com>
Date2020-12-04 22:55 -0600
SubjectRe: 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]


#26471 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2020-12-04 23:26 -0800
SubjectRe: 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]


#26479 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

Fromolcott <NoOne@NoWhere.com>
Date2020-12-05 09:54 -0600
SubjectRe: 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]


#26483 — Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2020-12-05 16:36 +0000
SubjectRe: 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