Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #79427
| From | Juha Nieminen <nospam@thanks.invalid> |
|---|---|
| Newsgroups | comp.theory, comp.lang.c, comp.lang.c++ |
| Subject | Re: Solution To The Halting Problem [ Accurate Review? ] |
| Date | 2021-05-06 12:18 +0000 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <s70mr0$1pln$1@gioia.aioe.org> (permalink) |
| References | (4 earlier) <WZadnSBeOsgVQhP9nZ2dnUU7-K3NnZ2d@giganews.com> <s6tbmm$fjp$1@gioia.aioe.org> <j9CdnULry9O5LA_9nZ2dnUU7-I-dnZ2d@giganews.com> <s6vecc$19h0$1@gioia.aioe.org> <s70e01$fak$2@einstein.home.woodall.me.uk> |
Cross-posted to 3 groups.
In comp.lang.c++ Tim Woodall <news001@woodall.me.uk> wrote: > On 2021-05-06, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote: >> On 5/5/2021 7:52 AM, olcott wrote: >>> 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? > > This is crazy. If everything is 32 bits (including memory being bounded > by 32 bit addressing) > then the halting problem for that subset of programs is trivially[1] > decidable on a 64 bit machine as the step function is computable. Rather obviously if the machine can only be in a finite number of different states, the problem is trivial: Simply check if a previous state has been reached or not. Of course such a solution is quite useless because it doesn't tell us much. The reason for this is that, for example, any binary "yes / no" problem actually becomes a trinary problem: "Yes / no / out of memory". All the interesting problems would fall into that last category, thus making it useless. (Even if some problem could be solved in the finite amount of space, they may take too long to check.) > [1] Where trivially means it will take a lot longer than the lifetime of > the universe to decide for some programs but it will decide eventually. I don't think "the lifetime of the universe" begins to even scratch the surface. I think a computer with an address space of just a few hundreds of bytes would take longer than the age of the universe to go through every possible state.
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