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


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

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

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.

Show all headers | View raw


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


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