Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C]

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.lang.c
Subject	Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C]
Date	2020-08-30 21:36 +0100
Organization	A noiseless patient Spider
Message-ID	<87eennswge.fsf@bsb.me.uk> (permalink)
References	<EZudneqAq4Cla9bCnZ2dnUU7-TnNnZ2d@giganews.com> <20200830120314.347@kylheku.com>

Show all headers | View raw

Kaz Kylheku <793-849-0957@kylheku.com> writes:

> On 2020-08-30, olcott <NoOne@NoWhere.com> wrote:
>> The end goal of this sequence of posts is to show that the basic "C"
>> programming language (without the "C" libraries) can be fully mapped to
>> an abstract model of computation that is equivalent to a Turing machine
>> in such a way that any Turing complete computation can be written in the
>> "C" programming language.
>
> Turing's infinite tape can be mapped to the <stdio.h> facility.
> The possible symbols on that tape can be mapped to characters,
> and the operations and positioning can be mapped to the available
> library operations.

I think (but it's hard to get answers) that Peter Olcott is only
considering what we'd call freestanding implementations here.

But, worse, he's not interested in simply showing that hosted C is
Turing complete by simulating a universal TM.  I think he aims to show
that "ordinary C" can be made Turing complete just by implementing it on
a Turing complete sub-system.

(BTW, even a IO-based UTM needs are bit of checking.  Functions like
fgetpos need to be allowed to fail.  I think the specification is plenty
loose enough for that since it says almost nothing about what failures
are permissible.)

>> When "C" is mapped to an abstract model of computation that can provide 
>> an arbitrary number of arbitrary length linked lists, then "C" acquires 
>
> In the absence of I/O, the C storage model is finite, and therefore not
> Turing complete. However, perhaps not quite.
>
> I had a discussion with this with someone who convinced me of the
> following: in C we can allocate automatic storage (informally,
> "local variables on the stack") via recursion. If we do this without
> taking the address of anything, then pointers do not appear in
> the program, and thus, in the abstract sense, we don't run into the
> issue of pointers being of finite width.  With that restriction, we have
> no random access (the program cannot access material in existing
> activation frames without returning to them).  Therefore what we have is
> a push-down automaton (PDA).  A PDA is strictly less powerful than a
> Turing machine. It contains an infinity in that it can push down as far
> as it needs to, but there are some computations that can't be carried
> out with a universal push down machine.

Hmm...  Modern C has threads and therefore more than one stack.  A PDA
with two stacks is Turing complete so there may be a way after all.
Nice one!

Often, things like IO and threads (unless wired into the language
syntax) are informally excluded when asking if language X is Turing
complete, but I don't think the rules of this particular game are clear.

There is, though, another way to argue about C.  Implement your UTM in
our all-too-finite C as, say, compiled by gcc.  If a computation fails
for lack of space, just get the gcc people to double the size of all the
pointers and try again.  Repeat as necessary, using pointers simulated
in software.  Each iteration can conform to the C standard, and since
you only need to be able to run terminating computations to be Turing
complete, one can show that there is (in theory) a C implementation that
can run any given computation.

Whether this quantifier fiddling is permitted ("∀ p in programs, ∃ C
compiler s.t. C runs p" is not the same as "∃ C compiler s.t. ∀ p in
programs, C runs p") depends on the rules of the game.  None of this is
as tidy and formal as it is with the various mathematical models of
computation.

<cut>
-- 
Ben.

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

Thread

Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-08-30 13:55 -0500
  Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Kaz Kylheku <793-849-0957@kylheku.com> - 2020-08-30 19:19 +0000
    Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Siri Cruise <chine.bleu@yahoo.com> - 2020-08-30 12:30 -0700
      Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-08-30 14:40 -0500
      Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Kaz Kylheku <793-849-0957@kylheku.com> - 2020-08-30 19:41 +0000
        Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-08-30 15:02 -0500
          Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-30 22:05 +0100
        Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Siri Cruise <chine.bleu@yahoo.com> - 2020-08-30 13:35 -0700
          Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-08-30 15:59 -0500
        Re: Transforming "C" into a Turing equivalent language 006 [credit to Kaz where credit is due] olcott <NoOne@NoWhere.com> - 2020-09-02 11:48 -0500
    Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-08-30 14:57 -0500
    Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-30 21:36 +0100
      Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-08-30 16:19 -0500
        Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-31 02:30 +0100
          Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-08-30 21:35 -0500
            Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-31 03:53 +0100
              Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-08-31 10:08 -0500
            Re: Transforming "C" into a Turing equivalent language 001 [x86 based halt decider] olcott <NoOne@NoWhere.com> - 2020-08-30 23:55 -0500
              Re: Transforming "C" into a Turing equivalent language 001 [x86 based halt decider] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-08-31 06:30 -0700
                Re: Transforming "C" into a Turing equivalent language 001 [x86 based halt decider] olcott <NoOne@NoWhere.com> - 2020-08-31 10:04 -0500
              Re: Transforming "C" into a Turing equivalent language 001 [x86 based halt decider] olcott <NoOne@NoWhere.com> - 2020-09-01 20:38 -0500
                Re: Transforming "C" into a Turing equivalent language 001 [x86 based halt decider] olcott <NoOne@NoWhere.com> - 2020-09-01 21:51 -0500
                Re: Transforming "C" into a Turing equivalent language 001 [x86 based halt decider] olcott <NoOne@NoWhere.com> - 2020-09-03 09:21 -0500
                Re: Transforming "C" into a Turing equivalent language 001 [x86 based halt decider] André G. Isaak <agisaak@gm.invalid> - 2020-09-03 12:05 -0600
                Re: Transforming "C" into a Turing equivalent language 001 [x86 based halt decider] olcott <NoOne@NoWhere.com> - 2020-09-03 16:39 -0500
            Transforming "C" into a Turing equivalent language 002 [Translating C to a unary TM] olcott <NoOne@NoWhere.com> - 2020-08-31 13:00 -0500
            Re: Transforming "C" into a Turing equivalent language 002 [Translating C to a unary TM] olcott <NoOne@NoWhere.com> - 2020-08-31 13:10 -0500
            Re: Transforming "C" into a Turing equivalent language 004 [x86 language mapped to unlimited integers] olcott <NoOne@NoWhere.com> - 2020-09-02 11:44 -0500
      Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-08-31 00:23 +0100
        Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-31 02:24 +0100
          Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-08-31 09:59 -0500
          Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-08-31 20:06 +0100
            Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-08-31 14:28 -0500
              Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-08-31 22:51 +0100
                Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-08-31 17:49 -0500
                Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-09-01 02:42 +0100
                Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-08-31 23:30 -0500
                Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-09-01 15:30 +0100
                Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-09-01 09:51 -0500
                Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-08-31 23:32 -0500
                Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-09-01 16:15 +0100
                Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-09-01 10:53 -0500
                Re: Transforming "C" into a Turing equivalent language 001 [x86_UTM trace] olcott <NoOne@NoWhere.com> - 2020-08-31 23:24 -0500
            Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-31 20:46 +0100
              Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-08-31 15:05 -0500
              Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-09-01 21:39 +0100
                Re: Transforming "C" into a Turing equivalent language 002 [HP proof refutation] olcott <NoOne@NoWhere.com> - 2020-09-01 17:00 -0500
                Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-09-01 17:46 -0500
                Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-09-02 00:51 +0100
                Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-09-01 18:58 -0500
                Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-09-01 20:40 -0500
            Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-08-31 20:19 -0400
              Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-09-01 01:37 +0100
        Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-08-30 20:35 -0500
    Re: Transforming "C" into a Turing equivalent language 005 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-09-02 11:20 -0500
      Re: Transforming "C" into a Turing equivalent language 005 [Providing unlimited memory access to C] Kaz Kylheku <793-849-0957@kylheku.com> - 2020-09-02 17:22 +0000
        Re: Transforming "C" into a Turing equivalent language 005 [Providing unlimited memory access to C] olcott <NoOne@NoWhere.com> - 2020-09-02 12:27 -0500
  Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-08-31 11:18 -0700
    Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Jorgen Grahn <grahn+nntp@snipabacken.se> - 2020-08-31 21:34 +0000
      Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] Juha Nieminen <nospam@thanks.invalid> - 2020-09-01 09:13 +0000
        Re: Transforming "C" into a Turing equivalent language 001 [Providing unlimited memory access to C] boltar@nuttyella.co.uk - 2020-09-01 09:24 +0000

csiph-web