Re: Getting Around the Halting Problem

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.theory, sci.logic
Subject	Re: Getting Around the Halting Problem
Date	2020-08-22 11:14 +0100
Organization	A noiseless patient Spider
Message-ID	<877dtr56o3.fsf@bsb.me.uk> (permalink)
References	(1 earlier) <20200820101012.181@kylheku.com> <rhmho9$emo$1@dont-email.me> <20200821085511.341@kylheku.com> <rhprei$ucj$1@dont-email.me> <rhq6li$f2a$1@dont-email.me>

Cross-posted to 2 groups.

Show all headers | View raw

Jeff Barnett <jbb@notatt.com> writes:

> On 8/21/2020 7:12 PM, Newberry wrote:
>> Kaz Kylheku wrote:
>>> On 2020-08-20, Newberry <newberryxy@gmail.com> wrote:
>>>> Kaz Kylheku wrote:
>>>>> On 2020-08-20, Newberry <newberryxy@gmail.com> wrote:
> <snip>
>> Well, I do not use the lambda calculus. In my paper I use pseudocode
>> with the understanding that it could be URM or, for that matter, any
>> programming lang with the proviso that integers and memory are
>> infinite. For some of us this approach is more intuitive.
>
> Why not really simplify? You have: 2 indefinite precision non-negative
> integers; instructions to increment and decrement those integers by 1;
> the ability to branch on zero in a specified register (one of the
> integers); and an unconditional branch. That's all you need if (my)
> memory serves me correctly.

The minimal machine combines the decrement and conditional branch:
decrement or branch on zero.  (This may have been what you meant as you
were not writing formally.)

-- 
Ben.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-19 19:32 -0700
  Re: Getting Around the Halting Problem R Kym Horsell <kym@kymhorsell.com> - 2020-08-20 02:42 +0000
  Re: Getting Around the Halting Problem Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-20 04:01 +0100
    Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-19 22:26 -0700
    Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-19 22:28 -0700
      Re: Getting Around the Halting Problem Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-20 12:56 +0100
  Re: Getting Around the Halting Problem olcott <NoOne@NoWhere.com> - 2020-08-19 22:04 -0500
  Re: Getting Around the Halting Problem Kaz Kylheku <793-849-0957@kylheku.com> - 2020-08-20 17:07 +0000
    Re: Getting Around the Halting Problem (abstract versus concrete) olcott <NoOne@NoWhere.com> - 2020-08-20 12:35 -0500
  Re: Getting Around the Halting Problem Kaz Kylheku <793-849-0957@kylheku.com> - 2020-08-20 17:34 +0000
    Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-20 12:08 -0700
      Re: Getting Around the Halting Problem Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-20 20:18 +0100
      Re: Getting Around the Halting Problem Kaz Kylheku <793-849-0957@kylheku.com> - 2020-08-20 19:18 +0000
        Re: Getting Around the Halting Problem olcott <NoOne@NoWhere.com> - 2020-08-20 14:30 -0500
        Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-20 12:46 -0700
        Re: Getting Around the Halting Problem R Kym Horsell <kym@kymhorsell.com> - 2020-08-20 23:54 +0000
      Re: Getting Around the Halting Problem R Kym Horsell <kym@kymhorsell.com> - 2020-08-20 23:43 +0000
      Re: Getting Around the Halting Problem Kaz Kylheku <793-849-0957@kylheku.com> - 2020-08-21 17:10 +0000
        Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-21 18:12 -0700
          Re: Getting Around the Halting Problem Jeff Barnett <jbb@notatt.com> - 2020-08-21 22:24 -0600
            Re: Getting Around the Halting Problem olcott <NoOne@NoWhere.com> - 2020-08-22 00:29 -0500
            Re: Getting Around the Halting Problem Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-22 11:14 +0100
              Re: Getting Around the Halting Problem Jeff Barnett <jbb@notatt.com> - 2020-08-22 12:05 -0600
    Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-23 10:15 -0700
      Re: Getting Around the Halting Problem Peter <peterxpercival@hotmail.com> - 2020-08-23 18:26 +0100
        Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-23 11:29 -0700
      Re: Getting Around the Halting Problem Kaz Kylheku <793-849-0957@kylheku.com> - 2020-08-24 01:06 +0000
        Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-23 21:26 -0700
  Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-22 20:39 -0700
    Re: Getting Around the Halting Problem R Kym Horsell <kym@kymhorsell.com> - 2020-08-23 07:44 +0000

csiph-web