Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #79448
| 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> |
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
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