Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #79388 > unrolled thread
| Started by | Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> |
|---|---|
| First post | 2021-05-02 14:15 +0100 |
| Last post | 2021-05-14 11:12 -0500 |
| Articles | 20 on this page of 47 — 12 participants |
Back to article view | Back to comp.lang.c++
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 →
| From | Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> |
|---|---|
| Date | 2021-05-02 14:15 +0100 |
| Subject | Solution 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]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2021-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]
| From | Richard Harnden <richard.nospam@gmail.com> |
|---|---|
| Date | 2021-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-04 19:41 -0500 |
| Subject | Re: 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]
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Date | 2021-05-05 00:55 +0000 |
| Subject | Re: 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]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2021-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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-02 10:30 -0500 |
| Subject | Re: 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]
| From | Real Troll <real.troll@trolls.com> |
|---|---|
| Date | 2021-05-02 17:01 +0100 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-02 12:21 -0500 |
| Subject | Re: 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]
| From | wij <wyniijj@gmail.com> |
|---|---|
| Date | 2021-05-02 12:04 -0700 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-02 15:08 -0500 |
| Subject | Re: 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]
| From | Christian Gollwitzer <auriocus@gmx.de> |
|---|---|
| Date | 2021-05-07 18:01 +0200 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-07 13:15 -0500 |
| Subject | Re: 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]
| From | Tim Woodall <news001@woodall.me.uk> |
|---|---|
| Date | 2021-05-07 20:33 +0000 |
| Subject | Re: 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]
| From | Christian Gollwitzer <auriocus@gmx.de> |
|---|---|
| Date | 2021-05-07 22:54 +0200 |
| Subject | Re: 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]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-05-07 23:35 +0100 |
| Subject | OT: 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]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2021-05-04 22:50 -0700 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-05 09:52 -0500 |
| Subject | Re: 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]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2021-05-05 17:48 -0700 |
| Subject | Re: 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]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-05 20:09 -0500 |
| Subject | Re: 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