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-31 02:24 +0100
Organization	A noiseless patient Spider
Message-ID	<87wo1fr4jy.fsf@bsb.me.uk> (permalink)
References	<EZudneqAq4Cla9bCnZ2dnUU7-TnNnZ2d@giganews.com> <20200830120314.347@kylheku.com> <87eennswge.fsf@bsb.me.uk> <y7CdnWTSOOxDqdHCnZ2dnUU78UHNnZ2d@brightview.co.uk>

Show all headers | View raw

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:

> On 30/08/2020 21:36, Ben Bacarisse wrote:
>> 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!
>
> Isn't it the case though, that
>
> -  In any C implementation (or C++) the size of a pointer is fixed
>
> -  Every distinct object (class/struct/variable/etc...) must have
>    its own unique address (that fits the pointer size)
> ?

Yes, indeed.  But I suspect the argument proposed to Kaz relies on what
is permitted when no addresses are used.  This imaginary implementation
would collapse in a heap (no pun intended) if any use were ever made of
an address.  The question being, is a C implementation obliged to
restrict the set of objects if the program takes no note of any pointers
and could therefore not tell?

Going the other way, it is widely considered acceptable for an
implementation to give distinct objects, with overlapping lifetimes, the
same address provided the program's observable behaviour is not
affected.

I'm not really inclined to "go to court" (either way) over this one!
The rules are not precise and the question is of no practical or
theoretical importance.  But I think it's fun the think about...

> If so any C implementation can only have finitely many distinct
> addressable objects, and so can not fully implement a TM tape, and can
> only in principle run a subset of TM calculations
>
> Of course, any C implementation can implement a partial TM emulator,
> and this might have the capacity to run interesting TM calculations,
> but it seems to me not all TM calculations.
>
> Sure, if we consider a sequence of C implementations with ever larger
> address pointer sizes, then given any /terminating/ TM calculation,
> eventually one of them will be capable of running it.  But some
> non-terminating TM calculations cannot run on a finite tape, so we're
> sort of loosing this theoretical battle.

Usually, (I thought) the relevant definitions are in terms of
terminating computations.  Failing on the ones that don't terminate is
no failure of completeness.  Mind you, I'd need to re-read someone like
Martin on this because I don't recall the technical definition.

> Now if we could change the C spec to allow variable length pointer
> sizes, then we would have a theoretically infinite pool of addressable
> objects, so suddenly a full TM emulator becomes easy in terms of
> theoretical program design, but obviously not when it comes to running
> on a given physical implementation, whose memory will only be
> finite. (But this probably doesn't matter for PO, who knows?
> Certainly not PO, who is quite lost in all this...)

That's one way, but it would need quite a few detailed of changes in the
language.  Another, rather arbitrary, way would be to allow at least two
unbounded integers.

> Or if we can use IO facilities then a potentially infinite virtual
> memory results - e.g. parts of the tape could be backed in a
> cloud-based system addressed through arbitrary long URLs.  (Ok, maybe
> URLs have a max length, but we can envisage some new storage device
> addressed through IO subsystem not having this restriction.

Though that steps outside of standard C.  The "standard" way would be to
use tmpfile, fseek(_, +1/-1, SEEK_CUR) and fread and fwrite to get a
one-ended unbounded  tape.

>> 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.
>
> Yes, for a given terminating calculation.  But to do this we just
> declare a big enough array to run the calculation, and run it.

Yes, you can switch larger integer indexes for larger pointers.  The two
views are interchangeable.  (Or have I missed the point you are
making?).

-- 
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