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 20:46 +0100
Organization	A noiseless patient Spider
Message-ID	<87d036ppiv.fsf@bsb.me.uk> (permalink)
References	(1 earlier) <20200830120314.347@kylheku.com> <87eennswge.fsf@bsb.me.uk> <y7CdnWTSOOxDqdHCnZ2dnUU78UHNnZ2d@brightview.co.uk> <87wo1fr4jy.fsf@bsb.me.uk> <-qCdnTbAXt6h19DCnZ2dnUU78XnNnZ2d@brightview.co.uk>

Show all headers | View raw

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

> On 31/08/2020 02:24, Ben Bacarisse wrote:
>> 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:
<cut>
>>>>> 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?
>
> Ah, right.  I hadn't been considering that.
>
> A sort of techie rules question and I don't have the official rules,
> but an interesting idea...

Yes, I don't think a definitive answer is possible.  I would be happy to
be sent in to bat for either team.  I think I could make a half decent
case either way.

> I'm more interested in the claim that having two stacks will give
> equivalent functionality to a full TM.  This is probably obvious once
> you see it, but is there a simple explanation for how this works?

Roughly speaking, going "left" is push(S2, pop(S1)) and going "right" is
push(S1, pop(S2)).  That way you get a one-ended unbounded tape.

>> 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.
>
> Makes sense, and we have a similar issue as with memory addresses -
> fseek has only a finite number of output values, but is it OK for an
> implementation to process larger files if fseek is never called?  (I'd
> guess yes...)

I think you mean ftell.  fseek does have a finite number of output
values but they signal only success/failure.

But you are right that it's a language lawyer kind of issue.  Is fseek
allowed to go beyond the range where ftell and/or fgetpos could possibly
work, and is the answer dependent on whether calls to those functions
appear in the code or not?  I'm pretty sure this one is a "yes" in both
cases.  I think ftell (and fgetpos) can simply fail at any time and for
any reason that the implementation decides on.

> My point was just that if PO's intention is simply to run a specific
> terminating calculation, then the issue becomes trivial, so no need
> for much discussion.  I think that /is/ his intention, because in the
> past he claimed to have a fully coded TM that "refuted the usual
> diagonal argument used in the TM halting problem proof".  Having
> admitted he doesn't have this, I think he now wants to claim he has a
> C program that refutes the equivalent diagonal argument for C
> programs.  Of course he cannot have this, as the diagonal argument
> demonstrates.

Ah, you are a great revelation behind the times.  He now has a halt
decider!  Not sure what it decides halting for, but he's gone beyond the
"one impossible case" from Dec 2018.  (BTW, was it you that pointed out
to me then that, despite his claiming to have "exactly Linz's H", he was
talking about only one M/M^ related pair and not a halt decider?  If so,
thanks.)

> I'm thinking I'll help PO by offering him a skeleton C program where
> all he needs to fill in is his implementation of his partial halt
> decider H (and possibly adjust how he wants to pass descriptions of
> TMs as parameters).  The skeleton will correctly implement H^ in terms
> of H to reduce the possibility of confusion on this point.  Who knows
> - when he sees the skeleton he may realise why his idea cannot
> possibly work, and even come to actually understand the proof he has
> supposedly been studying for 20(?) years!

Hmm...  He does not have a Turing machine on which the H to H^
transformation can be made.  He lied about that.  What he had in Dec
2018, it now turns out, was a "snippet of C like code".  Goodness knows
what he thinks it does.  But go for it.  You never know.

The truth of the matter is that he wants to talk about this stuff (and
to himself up in the process) and not much else.  I don't think he will
ever post this "snippet of C-like code".  All the subsequent posts are
attempts at distraction so he does not have to post it.

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