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


Groups > comp.lang.c++ > #79448

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

From Christian Gollwitzer <auriocus@gmx.de>
Newsgroups comp.lang.c++
Subject Re: Solution To The Halting Problem [ Accurate Review? ]
Date 2021-05-07 22:54 +0200
Organization A noiseless patient Spider
Message-ID <s749ev$ka6$1@dont-email.me> (permalink)
References (4 earlier) <WZadnSBeOsgVQhP9nZ2dnUU7-K3NnZ2d@giganews.com> <122b9d56-1c3e-4ad8-84ed-857ba37029cen@googlegroups.com> <QbydneMdYN1YmxL9nZ2dnUU7-XfNnZ2d@giganews.com> <s73o8i$g8u$1@dont-email.me> <s74873$hn3$1@einstein.home.woodall.me.uk>

Show all headers | View raw


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

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

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

csiph-web