Re: Mapping x86/x64/C to a Turing equivalent abstract model of computation

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.theory, comp.lang.c
Subject	Re: Mapping x86/x64/C to a Turing equivalent abstract model of computation
Date	2020-09-05 21:11 +0100
Organization	A noiseless patient Spider
Message-ID	<87eengdlvb.fsf@bsb.me.uk> (permalink)
References	<3PmdncMnu9yXIs7CnZ2dnUU7-KvNnZ2d@giganews.com> <3PmdncInu9w5Is7CnZ2dnUU7-KudnZ2d@giganews.com>

Cross-posted to 2 groups.

Show all headers | View raw

olcott <NoOne@NoWhere.com> writes:

> We can override and supersede the standard "C" and map its syntax and
> semantics to an abstract model of computation that is Turing
> equivalent.

If you were making a technical case, you would have to specify what it
is about C you intend to change in order to make it Turing complete.  If
you don't specify this new language, you might end up writing
bounded-memory programs without even realising it.

There are small but impractical changes to C that are, none the less,
theoretically sufficient (for example, C with two unbounded integer
variables with minimal arithmetic defined on them) but that would be
pointless.  You might as well then write directly for an unbounded
register machine.  All interesting programs would become hopelessly
convoluted rather than looking like natural code.

It would make more sense to remove from C all the things that result in
it being able to address only finite memory, or all the things that mean
its arithmetic types are bounded in size (or both, of course).  The
result would that programs written in this new language would look
relatively conventional.

That's an interesting student exercise, but not something that deserves
to be part of a serious investigation into compatibility.  For that
purpose, it would be wise to start with a notation that is (or is very
nearly) already Turing complete.

-- 
Ben.

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

Thread

Mapping "C" to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-05 11:38 -0500
  Mapping x86/x64/C to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-05 11:41 -0500
    Re: Mapping x86/x64/C to a Turing equivalent abstract model of computation Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-09-05 21:11 +0100
      Re: Mapping x86/x64/C to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-05 15:40 -0500
        Re: Mapping x86/x64/C to a Turing equivalent abstract model of computation Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-09-06 00:27 +0100
          Re: Mapping x86/x64/C to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-05 20:22 -0500
            Re: Mapping x86/x64/C to a Turing equivalent abstract model of computation André G. Isaak <agisaak@gm.invalid> - 2020-09-06 09:41 -0600
              Re: Mapping x86/x64/C to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-06 13:07 -0500
  Re: Mapping "C" to a Turing equivalent abstract model of computation Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-09-05 11:01 -0700
    Re: Mapping "C" to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-05 13:26 -0500
      Re: Mapping "C" to a Turing equivalent abstract model of computation Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-09-05 11:43 -0700
        Re: Mapping "C" to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-05 14:33 -0500
          Re: Mapping "C" to a Turing equivalent abstract model of computation Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-09-05 12:53 -0700
            Re: Mapping "C" to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-05 15:26 -0500
  Re: Mapping "C" to a Turing equivalent abstract model of computation Jeff Barnett <jbb@notatt.com> - 2020-09-08 11:18 -0600
    Re: Mapping "C" to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-08 12:30 -0500
      Re: Mapping "C" to a Turing equivalent abstract model of computation Jeff Barnett <jbb@notatt.com> - 2020-09-08 14:48 -0600
        Re: Mapping "C" to a Turing equivalent abstract model of computation olcott <NoOne@NoWhere.com> - 2020-09-08 16:34 -0500

csiph-web