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


Groups > comp.lang.c++ > #79388 > unrolled thread

Solution To The Halting Problem

Started byMr Flibble <flibble@i42.REMOVETHISBIT.co.uk>
First post2021-05-02 14:15 +0100
Last post2021-05-14 11:12 -0500
Articles 20 on this page of 47 — 12 participants

Back to article view | Back to comp.lang.c++


Contents

  Solution To The Halting Problem Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2021-05-02 14:15 +0100
    Re: Solution To The Halting Problem Kaz Kylheku <563-365-8930@kylheku.com> - 2021-05-02 14:03 +0000
      Re: Solution To The Halting Problem Richard Harnden <richard.nospam@gmail.com> - 2021-05-02 15:15 +0100
        Re: Solution To The Halting Problem [ C/x86 defines computable functions ] olcott <NoOne@NoWhere.com> - 2021-05-04 19:41 -0500
          Re: Solution To The Halting Problem [ C/x86 defines computable functions ] Kaz Kylheku <563-365-8930@kylheku.com> - 2021-05-05 00:55 +0000
      Re: Solution To The Halting Problem Bonita Montero <Bonita.Montero@gmail.com> - 2021-05-02 16:59 +0200
      Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-02 10:30 -0500
        Re: Solution To The Halting Problem [ Accurate Review? ] Real Troll <real.troll@trolls.com> - 2021-05-02 17:01 +0100
          Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-02 12:21 -0500
            Re: Solution To The Halting Problem [ Accurate Review? ] wij <wyniijj@gmail.com> - 2021-05-02 12:04 -0700
              Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-02 15:08 -0500
                Re: Solution To The Halting Problem [ Accurate Review? ] Christian Gollwitzer <auriocus@gmx.de> - 2021-05-07 18:01 +0200
                  Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-07 13:15 -0500
                  Re: Solution To The Halting Problem [ Accurate Review? ] Tim Woodall <news001@woodall.me.uk> - 2021-05-07 20:33 +0000
                    Re: Solution To The Halting Problem [ Accurate Review? ] Christian Gollwitzer <auriocus@gmx.de> - 2021-05-07 22:54 +0200
                    OT: decision problems Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-07 23:35 +0100
            Re: Solution To The Halting Problem [ Accurate Review? ] "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-04 22:50 -0700
              Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-05 09:52 -0500
                Re: Solution To The Halting Problem [ Accurate Review? ] "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-05 17:48 -0700
                  Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-05 20:09 -0500
                    Re: Solution To The Halting Problem [ Accurate Review? ] "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-05 18:27 -0700
                      Re: Solution To The Halting Problem [ Accurate Review? ] "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-07 00:34 -0700
                      Re: Solution To The Halting Problem [ Accurate Review? ] "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-05-16 15:08 -0700
                  Re: Solution To The Halting Problem [ Accurate Review? ] Tim Woodall <news001@woodall.me.uk> - 2021-05-06 09:47 +0000
                    Re: Solution To The Halting Problem [ Accurate Review? ] Juha Nieminen <nospam@thanks.invalid> - 2021-05-06 12:18 +0000
                      Re: Solution To The Halting Problem [ Accurate Review? ] Tim Woodall <news001@woodall.me.uk> - 2021-05-06 12:45 +0000
                      Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-06 09:17 -0500
                    Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-06 09:16 -0500
                      Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-06 10:52 -0500
                        Re: Solution To The Halting Problem [ Accurate Review? ] olcott <NoOne@NoWhere.com> - 2021-05-07 09:14 -0500
    Re: Solution To The Halting Problem Real Troll <real.troll@trolls.com> - 2021-05-02 16:20 +0100
    Re: Solution To The Halting Problem [ H based on UTM ]( correct answer ) olcott <NoOne@NoWhere.com> - 2021-05-06 11:03 -0500
      Re: New test program (succeeds) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-05-07 18:38 +0000
      Re: New test program (Succeeds V2) olcott <NoOne@NoWhere.com> - 2021-05-07 16:13 -0500
        Re: New test program (Succeeds V2)(Ben contradicts himself) olcott <NoOne@NoWhere.com> - 2021-05-08 11:18 -0500
        Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) olcott <NoOne@NoWhere.com> - 2021-05-08 17:45 -0500
          Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) wij <wyniijj@gmail.com> - 2021-05-08 19:21 -0700
            Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) olcott <NoOne@NoWhere.com> - 2021-05-08 21:35 -0500
              Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) wij <wyniijj@gmail.com> - 2021-05-08 20:02 -0700
                Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) olcott <NoOne@NoWhere.com> - 2021-05-08 22:11 -0500
                  Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) wij <wyniijj@gmail.com> - 2021-05-08 20:55 -0700
                    Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) olcott <NoOne@NoWhere.com> - 2021-05-08 23:07 -0500
                      Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2021-05-09 19:18 +0100
                      Re: New test program (Succeeds V2)[ Honest Dialogue? ]( maybe not ) wij <wyniijj@gmail.com> - 2021-05-09 12:15 -0700
          Re: New test program (Succeeds V2)[ Mike is a good technical reviewer ] olcott <NoOne@NoWhere.com> - 2021-05-10 14:36 -0500
    Re: New test program (Succeeds V2)[ counter-example in C ? ] olcott <NoOne@NoWhere.com> - 2021-05-12 15:45 -0500
      Re: New test program (Succeeds V2)[ entirely different computation ] olcott <NoOne@NoWhere.com> - 2021-05-14 11:12 -0500

Page 1 of 3  [1] 2 3  Next page →


#79388 — Solution To The Halting Problem

FromMr Flibble <flibble@i42.REMOVETHISBIT.co.uk>
Date2021-05-02 14:15 +0100
SubjectSolution To The Halting Problem
Message-ID<eCxjI.450528$AWcd.220764@fx42.ams4>
Does anyone know the solution to the problem of halting olcott's Usenet posts?

/Flibble

-- 
😎

[toc] | [next] | [standalone]


#79389

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-05-02 14:03 +0000
Message-ID<20210502070155.115@kylheku.com>
In reply to#79388
On 2021-05-02, Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> wrote:
> Does anyone know the solution to the problem of halting olcott's Usenet posts?

Everyone halts. For this case, specifically, there is an unproven
and empirically untested hypothesis about an early halt that occurs
if everyone stops responding.

-- 
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal

[toc] | [prev] | [next] | [standalone]


#79390

FromRichard Harnden <richard.nospam@gmail.com>
Date2021-05-02 15:15 +0100
Message-ID<s6mc6o$n39$1@dont-email.me>
In reply to#79389
On 02/05/2021 15:03, Kaz Kylheku wrote:
> On 2021-05-02, Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> wrote:
>> Does anyone know the solution to the problem of halting olcott's Usenet posts?
> 
> Everyone halts. For this case, specifically, there is an unproven
> and empirically untested hypothesis about an early halt that occurs
> if everyone stops responding.
> 

We can ask him to stop.  We can't prove that he will.

[toc] | [prev] | [next] | [standalone]


#79415 — Re: Solution To The Halting Problem [ C/x86 defines computable functions ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-04 19:41 -0500
SubjectRe: Solution To The Halting Problem [ C/x86 defines computable functions ]
Message-ID<JOKdnYcamOgidAz9nZ2dnUU7-LXNnZ2d@giganews.com>
In reply to#79390
On 5/4/2021 2:24 PM, Kaz Kylheku wrote:
> ["Followup-To:" header set to comp.theory.]
> On 2021-05-04, olcott <NoOne@NoWhere.com> wrote:
>> On 5/4/2021 12:06 PM, Kaz Kylheku wrote:
>>> On 2021-05-04, olcott <NoOne@NoWhere.com> wrote:
>>>> On 5/3/2021 6:27 PM, Ben Bacarisse wrote:
>>>>> Did you have a question about what I wrote?  You seem to be having
>>>>> trouble understanding it.
>>>>>
>>>>
>>>> The notion of data passed to a function in the x86 architecture has zero
>>>
>>> There is no "function" in x86. Some assemblers for x86 in fact have
>>> pseudo-ops for delimiting a procedure using syntax like "PROC FAR" and
>>> "ENDP".
>>>
>>
>> Computable Functions
>> A Turing machine computes a function by starting with the input to the
>> function on the tape and halting with the output of the function on the
>> tape.  (Sipser:1997:190)
> 
> And nothing but the tape, so help you god.
> 
> Each call Halts(P, P) is a new Turing machine, where the tape contents
> depend only on Halts and P, and not any global execution traces gathered
> by a larger surrouding machine.
> 

int Halts(u32 P, u32 I)
{
   Simulate(P,I) until decided not halts or halts.
   if decided not halts return 0.
   else return 1.
}

>> When we unify on the Sipser and Kozen definitions of "computable
>> function" we have the mapping from one possibly empty finite string to
>> another possibly empty finite string.
> 
> Sure, and when Halts is invoked in you apparatus with apparently the
> same formal arguments, it does not represent the same mapping each time,
> as required.
> 
> The tape is different each time. Since the arguments are not, and
> the function is the same, it means that the tape contains something
> not coming from the arguments.
> 
> That arrangement cannot refute a proof in which it is critically
> important that the corresponding computations are one and the same.
> 
>> It seems that we can define this in terms of a generic model of
> 
> Well, things are not as they seem. If you were confident, you wouldn't
> use weasel words like "seem", would you.
> 
>> computation as a machine that computes the mapping from one possibly
>> empty finite string input to another possibly empty finite string output
>> and and then halts.
>>
>> A C function that returns a 0 or 1 value on the basis of an input finite
>> string pair would meet the above definition of computable function.
> 
> It could, but not necessarily so. To write a C function that behaves
> like function, in particular a function of the arguments given to its
> formal parameters, we have to follow certain coding rules.
> 
> Your apparatus does not follow those rules.
> 
> (By your own admission, Halts is not even an ordinary C function
> in the first place, but a special operator of the "x86 UTM".)
> 


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#79416 — Re: Solution To The Halting Problem [ C/x86 defines computable functions ]

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-05-05 00:55 +0000
SubjectRe: Solution To The Halting Problem [ C/x86 defines computable functions ]
Message-ID<20210504174836.394@kylheku.com>
In reply to#79415
["Followup-To:" header set to comp.theory.]
On 2021-05-05, olcott <NoOne@NoWhere.com> wrote:
> On 5/4/2021 2:24 PM, Kaz Kylheku wrote:
>> ["Followup-To:" header set to comp.theory.]
>> On 2021-05-04, olcott <NoOne@NoWhere.com> wrote:
>>> On 5/4/2021 12:06 PM, Kaz Kylheku wrote:
>>>> On 2021-05-04, olcott <NoOne@NoWhere.com> wrote:
>>>>> On 5/3/2021 6:27 PM, Ben Bacarisse wrote:
>>>>>> Did you have a question about what I wrote?  You seem to be having
>>>>>> trouble understanding it.
>>>>>>
>>>>>
>>>>> The notion of data passed to a function in the x86 architecture has zero
>>>>
>>>> There is no "function" in x86. Some assemblers for x86 in fact have
>>>> pseudo-ops for delimiting a procedure using syntax like "PROC FAR" and
>>>> "ENDP".
>>>>
>>>
>>> Computable Functions
>>> A Turing machine computes a function by starting with the input to the
>>> function on the tape and halting with the output of the function on the
>>> tape.  (Sipser:1997:190)
>> 
>> And nothing but the tape, so help you god.
>> 
>> Each call Halts(P, P) is a new Turing machine, where the tape contents
>> depend only on Halts and P, and not any global execution traces gathered
>> by a larger surrouding machine.
>> 
>
> int Halts(u32 P, u32 I)
> {
>    Simulate(P,I) until decided not halts or halts.
>    if decided not halts return 0.
>    else return 1.
> }

All you're showing is that Halts is a wrapper for Simulate.

OK, so the problem is coming from Simulate.

Simulate does not decide the same arguments the same way each time.

It depends on existing values global variables such as buffers of
execution traces.

To meet the conditions of the halting proof, any such globals must be
reset to the same state before Simulate is called.

[toc] | [prev] | [next] | [standalone]


#79391

FromBonita Montero <Bonita.Montero@gmail.com>
Date2021-05-02 16:59 +0200
Message-ID<s6meo0$9i3$1@dont-email.me>
In reply to#79389
>> Does anyone know the solution to the problem of halting olcott's Usenet posts?

> Everyone halts. For this case, specifically, there is an unproven
> and empirically untested hypothesis about an early halt that occurs
> if everyone stops responding.

The only halting-problem is whether he will halt to post off-topic
issues to comp.lang.c/c++.

[toc] | [prev] | [next] | [standalone]


#79393 — Re: Solution To The Halting Problem [ Accurate Review? ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-02 10:30 -0500
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<DbmdnedlULb8WBP9nZ2dnUU7-c3NnZ2d@giganews.com>
In reply to#79389
On 5/2/2021 9:03 AM, Kaz Kylheku wrote:
> On 2021-05-02, Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> wrote:
>> Does anyone know the solution to the problem of halting olcott's Usenet posts?
> 
> Everyone halts. For this case, specifically, there is an unproven
> and empirically untested hypothesis about an early halt that occurs
> if everyone stops responding.
> 

I am going to continue to post until an accurate review proves that I a 
right or proves that I am wrong. This will remain true even if no one on 
this forum ever responds. In this case the reason for posting is to 
establish my copyright ownership of every incremental improvement.

Occasional cross-posts are for redundant backup of my key ideas

The bigger question is when are my reviewers going to provide an 
accurate review?

It is a fact that this infinite recursion detection criteria is correct:

If the execution trace of function Y() shows:
function X() is called twice in sequence from the same machine address 
of Y()
with the same parameters to X()
with no conditional branch or indexed jump instructions in Y()
with no function call returns from X()
then the function call from Y() to X() is infinitely recursive.

It is a fact that this criteria correctly  decides all calls from 
H_Hat() to Halts() are infinitely recursive:

If the execution trace of H_Hat() by function Halts() shows:
(1) Function Halts() is called twice in sequence from the same machine 
address of H_Hat().
(2) With the same parameters to Halts().
(3) With no conditional branch or indexed jump instructions in H_Hat().
(4) With no function call returns from Halts().
then the function call from H_Hat() to Halts() is infinitely recursive.

void H_Hat(u32 P)
{
  u32 Input_Halts = Halts(P, P);
  if (Input_Halts)
    HERE: goto HERE;
}

int main()
{
  u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
  Output("Input_Would_Halt = ", Input_Would_Halt);
}

All of the details including a fresh execution trace are provided here:

http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf



-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#79394 — Re: Solution To The Halting Problem [ Accurate Review? ]

FromReal Troll <real.troll@trolls.com>
Date2021-05-02 17:01 +0100
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<s6mih4$12k7$1@gioia.aioe.org>
In reply to#79393
> I am going to continue to post until an accurate review proves that I 
> a right or proves that I am wrong.


Don't be sure about that because people will get fed up of you and write to your NewsServer provider:

<
abuse@giganews.com
 >

So be very careful before you test people's tolerance threshold here.



[toc] | [prev] | [next] | [standalone]


#79395 — Re: Solution To The Halting Problem [ Accurate Review? ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-02 12:21 -0500
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<WZadnSBeOsgVQhP9nZ2dnUU7-K3NnZ2d@giganews.com>
In reply to#79394
On 5/2/2021 11:01 AM, Real Troll wrote:
> 
>> I am going to continue to post until an accurate review proves that I 
>> a right or proves that I am wrong.
> 
> 
> Don't be sure about that because people will get fed up of you and write 
> to your NewsServer provider:
> 
> <
> abuse@giganews.com
>>
> 
> So be very careful before you test people's tolerance threshold here.
> 

Since all of my posts have the analysis of "C" code as their primary 
focus, none of my posts can be reasonably construed as off topic for C 
or C++ groups.

This is the "C" code that is the primary focus of all of my posts:

void H_Hat(u32 P)
{
   u32 Input_Halts = Halts(P, P);
   if (Input_Halts)
     HERE: goto HERE;
}

int main() {
   u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
   Output("Input_Would_Halt = ", Input_Would_Halt);
}

Can a C/C++ function be defined that correctly decides whether or not 
H_Hat((u32)H_Hat) halts?

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#79396 — Re: Solution To The Halting Problem [ Accurate Review? ]

Fromwij <wyniijj@gmail.com>
Date2021-05-02 12:04 -0700
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<122b9d56-1c3e-4ad8-84ed-857ba37029cen@googlegroups.com>
In reply to#79395
On Monday, 3 May 2021 at 01:21:31 UTC+8, olcott wrote:
> On 5/2/2021 11:01 AM, Real Troll wrote: 
> > 
> >> I am going to continue to post until an accurate review proves that I 
> >> a right or proves that I am wrong. 
> > 
> > 
> > Don't be sure about that because people will get fed up of you and write 
> > to your NewsServer provider: 
> > 
> > < 
> > ab...@giganews.com 
> >> 
> > 
> > So be very careful before you test people's tolerance threshold here. 
> >
> Since all of my posts have the analysis of "C" code as their primary 
> focus, none of my posts can be reasonably construed as off topic for C 
> or C++ groups. 
> 
> This is the "C" code that is the primary focus of all of my posts:
> void H_Hat(u32 P) 
> { 
> u32 Input_Halts = Halts(P, P); 
> if (Input_Halts) 
> HERE: goto HERE; 
> } 
> 
> int main() { 
> u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat); 
> Output("Input_Would_Halt = ", Input_Would_Halt); 
> }
> Can a C/C++ function be defined that correctly decides whether or not 
> H_Hat((u32)H_Hat) halts?
> -- 
> Copyright 2021 Pete Olcott 
> 
> "Great spirits have always encountered violent opposition from mediocre 
> minds." Einstein

I have not really read all your posts, and still do not really understand the appeal
of your question. So far as I understand:

Y() (H_Hat(u32)) can be written such that X() (Halts(u32,u32)) has no way 
recognizing being simulated...(Why so much focus on recursions?)

Another one has nothing to do with 'pathological form'

// [Return] true (n is even): There exist two prime numbers a,b such that n=a+b
//               false:  Otherwise
bool is_goldbach(BigNum n);

void Y() {
 for(BigNum n=4; is_goldbach(n); n+=2) {
 }
}

Can your halting decider program decide whether or not Y() terminate?

[toc] | [prev] | [next] | [standalone]


#79398 — Re: Solution To The Halting Problem [ Accurate Review? ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-02 15:08 -0500
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<QbydneMdYN1YmxL9nZ2dnUU7-XfNnZ2d@giganews.com>
In reply to#79396
On 5/2/2021 2:04 PM, wij wrote:
> On Monday, 3 May 2021 at 01:21:31 UTC+8, olcott wrote:
>> On 5/2/2021 11:01 AM, Real Troll wrote:
>>>
>>>> I am going to continue to post until an accurate review proves that I
>>>> a right or proves that I am wrong.
>>>
>>>
>>> Don't be sure about that because people will get fed up of you and write
>>> to your NewsServer provider:
>>>
>>> <
>>> ab...@giganews.com
>>>>
>>>
>>> So be very careful before you test people's tolerance threshold here.
>>>
>> Since all of my posts have the analysis of "C" code as their primary
>> focus, none of my posts can be reasonably construed as off topic for C
>> or C++ groups.
>>
>> This is the "C" code that is the primary focus of all of my posts:
>> void H_Hat(u32 P)
>> {
>> u32 Input_Halts = Halts(P, P);
>> if (Input_Halts)
>> HERE: goto HERE;
>> }
>>
>> int main() {
>> u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
>> Output("Input_Would_Halt = ", Input_Would_Halt);
>> }
>> Can a C/C++ function be defined that correctly decides whether or not
>> H_Hat((u32)H_Hat) halts?
>> -- 
>> Copyright 2021 Pete Olcott
>>
>> "Great spirits have always encountered violent opposition from mediocre
>> minds." Einstein
> 
> I have not really read all your posts, and still do not really understand the appeal
> of your question. So far as I understand:
> 
> Y() (H_Hat(u32)) can be written such that X() (Halts(u32,u32)) has no way
> recognizing being simulated...(Why so much focus on recursions?)
> 
> Another one has nothing to do with 'pathological form'
> 

My halt decider does correctly decide the simplest example of the 
halting problem undecidability proof counter-examples that are supposed 
to "prove" that a universal halt decider is impossible:

void H_Hat(u32 P)
{
   u32 Input_Halts = Halts(P, P);
   if (Input_Halts)
     HERE: goto HERE;
}

int main()
{
   u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
   Output("Input_Would_Halt = ", Input_Would_Halt);
}

All of the details including a full x86 execution trace are in this paper:

http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf


> // [Return] true (n is even): There exist two prime numbers a,b such that n=a+b
> //               false:  Otherwise
> bool is_goldbach(BigNum n);
> 
> void Y() {
>   for(BigNum n=4; is_goldbach(n); n+=2) {
>   }
> }
> 
> Can your halting decider program decide whether or not Y() terminate?
> 

I am not going to begin to look at these things until after my first 
proof is accepted as correct or proven to be incorrect.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#79443 — Re: Solution To The Halting Problem [ Accurate Review? ]

FromChristian Gollwitzer <auriocus@gmx.de>
Date2021-05-07 18:01 +0200
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<s73o8i$g8u$1@dont-email.me>
In reply to#79398
Am 02.05.21 um 22:08 schrieb olcott:
>> // [Return] true (n is even): There exist two prime numbers a,b such 
>> that n=a+b
>> //               false:  Otherwise
>> bool is_goldbach(BigNum n);
>>
>> void Y() {
>>   for(BigNum n=4; is_goldbach(n); n+=2) {
>>   }
>> }
>>
>> Can your halting decider program decide whether or not Y() terminate?
>>
> 
> I am not going to begin to look at these things until after my first 
> proof is accepted as correct or proven to be incorrect.

Then you haven't understood the point. This program demonstrates that 
your halt decider, if it actually works, can decide the Goldbach 
conjecture (which is an unsolved problem in maths today).

So it is far more likely that your halt decider is wrong than that it 
solves the Goldbach conjecture. In fact, by extending on the idea, if a 
correct halt decider would exist, it could be used to prove *any* such 
conjecture about the natural numbers.

	
	Christian

[toc] | [prev] | [next] | [standalone]


#79445 — Re: Solution To The Halting Problem [ Accurate Review? ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-07 13:15 -0500
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<R7-dnX8nC6EBHgj9nZ2dnUU7-RXNnZ2d@giganews.com>
In reply to#79443
On 5/7/2021 11:01 AM, Christian Gollwitzer wrote:
> Am 02.05.21 um 22:08 schrieb olcott:
>>> // [Return] true (n is even): There exist two prime numbers a,b such 
>>> that n=a+b
>>> //               false:  Otherwise
>>> bool is_goldbach(BigNum n);
>>>
>>> void Y() {
>>>   for(BigNum n=4; is_goldbach(n); n+=2) {
>>>   }
>>> }
>>>
>>> Can your halting decider program decide whether or not Y() terminate?
>>>
>>
>> I am not going to begin to look at these things until after my first 
>> proof is accepted as correct or proven to be incorrect.
> 
> Then you haven't understood the point. This program demonstrates that 
> your halt decider, if it actually works, can decide the Goldbach 
> conjecture (which is an unsolved problem in maths today).
> 

Yes and in this same way we can make a program that only halts when it 
knows what Donald Trump has for lunch two years from now.

Such a halt decider would solve the "predicting the future" problem.

> So it is far more likely that your halt decider is wrong than that it 
> solves the Goldbach conjecture. In fact, by extending on the idea, if a 
> correct halt decider would exist, it could be used to prove *any* such 
> conjecture about the natural numbers.
> 
> 
>      Christian




-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#79447 — Re: Solution To The Halting Problem [ Accurate Review? ]

FromTim Woodall <news001@woodall.me.uk>
Date2021-05-07 20:33 +0000
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<s74873$hn3$1@einstein.home.woodall.me.uk>
In reply to#79443
On 2021-05-07, Christian Gollwitzer <auriocus@gmx.de> wrote:
>
> So it is far more likely that your halt decider is wrong than that it 
> solves the Goldbach conjecture. In fact, by extending on the idea, if a 
> correct halt decider would exist, it could be used to prove *any* such 
> conjecture about the natural numbers.
>

AIUI, there is no known 'halting proof' of the Collatz conjecture.

I'm not enough of a mathematician to say I have a gut feeling but I
wouldn't be surprised to learn that there are far more decision problems
that cannot be answered by a halting decider than that can be answered.

[toc] | [prev] | [next] | [standalone]


#79448 — Re: Solution To The Halting Problem [ Accurate Review? ]

FromChristian Gollwitzer <auriocus@gmx.de>
Date2021-05-07 22:54 +0200
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<s749ev$ka6$1@dont-email.me>
In reply to#79447
Am 07.05.21 um 22:33 schrieb Tim Woodall:
> On 2021-05-07, Christian Gollwitzer <auriocus@gmx.de> wrote:
>>
>> So it is far more likely that your halt decider is wrong than that it
>> solves the Goldbach conjecture. In fact, by extending on the idea, if a
>> correct halt decider would exist, it could be used to prove *any* such
>> conjecture about the natural numbers.
>>
> 
> AIUI, there is no known 'halting proof' of the Collatz conjecture.
> 
> I'm not enough of a mathematician to say I have a gut feeling but I
> wouldn't be surprised to learn that there are far more decision problems
> that cannot be answered by a halting decider than that can be answered.

Of course you are right, it can not prove any such theorem. Correctly 
stated:

If a program P exists which decides the truth of a given hypothesis for 
any natural number N in finite time, then the halt decider could be used 
to decide if the hypothesis is true for all natural numbers by running 
it on the code

void test() {

for (int i=1; P(i); i++) {}

}

That would still be a mighty tool. As for the Collatz conjecture, we 
would need to nest it. The Collatz conjecture for number N is true, if 
the sequence arrives at 1, so we use the halt decider to check whether 
the sequence comes to an end, and this then goes into the test function 
above. This is very simlar as the regular proof with the contradicting 
halting program, that no such decider can exist.

I like the Goldbach thing more because it does not need to 
self-reference the halt decider.

	Christian

[toc] | [prev] | [next] | [standalone]


#79451 — OT: decision problems

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-05-07 23:35 +0100
SubjectOT: decision problems
Message-ID<87tunemauc.fsf_-_@bsb.me.uk>
In reply to#79447
I've set followup-to in case this off topic subthread continues...

Tim Woodall <news001@woodall.me.uk> writes:

> I'm not enough of a mathematician to say I have a gut feeling but I
> wouldn't be surprised to learn that there are far more decision problems
> that cannot be answered by a halting decider than that can be
> answered.

Yes.  Formally, decision problems are really about decidable subsets of
N.  A set of natural numbers, D, is decidable iff there is a Turing
machine that, for every n in N, halts and accepts if n is in D, and
halts and rejects if n is not in D.

Since there are uncountably many subsets of N, and only countably many
Turing machines, what you say is correct.  A similar point was made
Turing in his 1936 paper: almost all real numbers are not computable.

If, however, you insist that a decision problem be written down as a
finite string using a finite alphabet, then the answer is different!

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#79419 — Re: Solution To The Halting Problem [ Accurate Review? ]

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2021-05-04 22:50 -0700
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<s6tbmm$fjp$1@gioia.aioe.org>
In reply to#79395
On 5/2/2021 10:21 AM, olcott wrote:
> On 5/2/2021 11:01 AM, Real Troll wrote:
>>
>>> I am going to continue to post until an accurate review proves that I 
>>> a right or proves that I am wrong.
>>
>>
>> Don't be sure about that because people will get fed up of you and 
>> write to your NewsServer provider:
>>
>> <
>> abuse@giganews.com
>>>
>>
>> So be very careful before you test people's tolerance threshold here.
>>
> 
> Since all of my posts have the analysis of "C" code as their primary 
> focus, none of my posts can be reasonably construed as off topic for C 
> or C++ groups.
> 
> This is the "C" code that is the primary focus of all of my posts:
> 
> void H_Hat(u32 P)
> {
>    u32 Input_Halts = Halts(P, P);
>    if (Input_Halts)
>      HERE: goto HERE;
> }
> 
> int main() {
>    u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
>    Output("Input_Would_Halt = ", Input_Would_Halt);
> }
> 
> Can a C/C++ function be defined that correctly decides whether or not 
> H_Hat((u32)H_Hat) halts?
> 

One suggestion... use a proper function pointer?

[toc] | [prev] | [next] | [standalone]


#79422 — Re: Solution To The Halting Problem [ Accurate Review? ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-05 09:52 -0500
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<j9CdnULry9O5LA_9nZ2dnUU7-I-dnZ2d@giganews.com>
In reply to#79419
On 5/5/2021 12:50 AM, Chris M. Thomasson wrote:
> On 5/2/2021 10:21 AM, olcott wrote:
>> On 5/2/2021 11:01 AM, Real Troll wrote:
>>>
>>>> I am going to continue to post until an accurate review proves that 
>>>> I a right or proves that I am wrong.
>>>
>>>
>>> Don't be sure about that because people will get fed up of you and 
>>> write to your NewsServer provider:
>>>
>>> <
>>> abuse@giganews.com
>>>>
>>>
>>> So be very careful before you test people's tolerance threshold here.
>>>
>>
>> Since all of my posts have the analysis of "C" code as their primary 
>> focus, none of my posts can be reasonably construed as off topic for C 
>> or C++ groups.
>>
>> This is the "C" code that is the primary focus of all of my posts:
>>
>> void H_Hat(u32 P)
>> {
>>    u32 Input_Halts = Halts(P, P);
>>    if (Input_Halts)
>>      HERE: goto HERE;
>> }
>>
>> int main() {
>>    u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
>>    Output("Input_Would_Halt = ", Input_Would_Halt);
>> }
>>
>> Can a C/C++ function be defined that correctly decides whether or not 
>> H_Hat((u32)H_Hat) halts?
>>
> 
> One suggestion... use a proper function pointer?

I have to force everything to be 32 bits.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#79423 — Re: Solution To The Halting Problem [ Accurate Review? ]

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2021-05-05 17:48 -0700
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<s6vecc$19h0$1@gioia.aioe.org>
In reply to#79422
On 5/5/2021 7:52 AM, olcott wrote:
> On 5/5/2021 12:50 AM, Chris M. Thomasson wrote:
>> On 5/2/2021 10:21 AM, olcott wrote:
>>> On 5/2/2021 11:01 AM, Real Troll wrote:
>>>>
>>>>> I am going to continue to post until an accurate review proves that 
>>>>> I a right or proves that I am wrong.
>>>>
>>>>
>>>> Don't be sure about that because people will get fed up of you and 
>>>> write to your NewsServer provider:
>>>>
>>>> <
>>>> abuse@giganews.com
>>>>>
>>>>
>>>> So be very careful before you test people's tolerance threshold here.
>>>>
>>>
>>> Since all of my posts have the analysis of "C" code as their primary 
>>> focus, none of my posts can be reasonably construed as off topic for 
>>> C or C++ groups.
>>>
>>> This is the "C" code that is the primary focus of all of my posts:
>>>
>>> void H_Hat(u32 P)
>>> {
>>>    u32 Input_Halts = Halts(P, P);
>>>    if (Input_Halts)
>>>      HERE: goto HERE;
>>> }
>>>
>>> int main() {
>>>    u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
>>>    Output("Input_Would_Halt = ", Input_Would_Halt);
>>> }
>>>
>>> Can a C/C++ function be defined that correctly decides whether or not 
>>> H_Hat((u32)H_Hat) halts?
>>>
>>
>> One suggestion... use a proper function pointer?
> 
> I have to force everything to be 32 bits.
> 

Does your simulator force this? How does it handle simulating C code 
that uses function pointers?

[toc] | [prev] | [next] | [standalone]


#79424 — Re: Solution To The Halting Problem [ Accurate Review? ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-05 20:09 -0500
SubjectRe: Solution To The Halting Problem [ Accurate Review? ]
Message-ID<ZvCdnWH9euoC3A79nZ2dnUU7-XvNnZ2d@giganews.com>
In reply to#79423
On 5/5/2021 7:48 PM, Chris M. Thomasson wrote:
> On 5/5/2021 7:52 AM, olcott wrote:
>> On 5/5/2021 12:50 AM, Chris M. Thomasson wrote:
>>> On 5/2/2021 10:21 AM, olcott wrote:
>>>> On 5/2/2021 11:01 AM, Real Troll wrote:
>>>>>
>>>>>> I am going to continue to post until an accurate review proves 
>>>>>> that I a right or proves that I am wrong.
>>>>>
>>>>>
>>>>> Don't be sure about that because people will get fed up of you and 
>>>>> write to your NewsServer provider:
>>>>>
>>>>> <
>>>>> abuse@giganews.com
>>>>>>
>>>>>
>>>>> So be very careful before you test people's tolerance threshold here.
>>>>>
>>>>
>>>> Since all of my posts have the analysis of "C" code as their primary 
>>>> focus, none of my posts can be reasonably construed as off topic for 
>>>> C or C++ groups.
>>>>
>>>> This is the "C" code that is the primary focus of all of my posts:
>>>>
>>>> void H_Hat(u32 P)
>>>> {
>>>>    u32 Input_Halts = Halts(P, P);
>>>>    if (Input_Halts)
>>>>      HERE: goto HERE;
>>>> }
>>>>
>>>> int main() {
>>>>    u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
>>>>    Output("Input_Would_Halt = ", Input_Would_Halt);
>>>> }
>>>>
>>>> Can a C/C++ function be defined that correctly decides whether or 
>>>> not H_Hat((u32)H_Hat) halts?
>>>>
>>>
>>> One suggestion... use a proper function pointer?
>>
>> I have to force everything to be 32 bits.
>>
> 
> Does your simulator force this? How does it handle simulating C code 
> that uses function pointers?

I created the x86utm operating system so that the halting problem could 
be explored using the much higher level languages of C and x86.

http://www.liarparadox.org/Halting_problem_undecidability_and_infinite_recursion.pdf

32-bit function pointers are generally cast into unsigned 32-bit 
integers to more closely correspond to an actual Turing machine.

Most anything that can be written 32-bit in C can probably be executed 
in x86utm because the x86 emulator is quite robust. The one thing that 
is excluded is linked libraries. The x86utm operating system directly 
executes COFF object files that have not been linked to libraries.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.c++


csiph-web