Re: Transforming "C" into a Turing equivalent language 004 [x86 language mapped to unlimited integers]

Subject	Re: Transforming "C" into a Turing equivalent language 004 [x86 language mapped to unlimited integers]
Newsgroups	comp.theory, comp.lang.c
References	(4 earlier) <87o8mrr48v.fsf@bsb.me.uk> <r4qdnWZZQdZl_NHCnZ2dnUU7-S3NnZ2d@giganews.com> <riiefr$1086$1@gioia.aioe.org> <P_WdnQV8g_tzYtHCnZ2dnUU7-audnZ2d@giganews.com> <rij90v$1mj2$1@gioia.aioe.org>
From	olcott <NoOne@NoWhere.com>
Date	2020-09-02 11:44 -0500
Message-ID	<fO2dnaOvh5x-VtLCnZ2dnUU7-evNnZ2d@giganews.com> (permalink)

Cross-posted to 2 groups.

Show all headers | View raw

On 8/31/2020 11:37 AM, Andy Walker wrote:
> On 31/08/2020 14:49, olcott wrote:
>> On 8/31/2020 4:05 AM, Andy Walker wrote:
>>> On 31/08/2020 03:35, olcott wrote:
>>>> Since the task of making a "C" to conventional five-tuple Turing
>>>> Machine translator is very difficult [...].
>>>      No it isn't.  Any competent CS graduate should be able to do it
>>> in a few days.  But it's tedious rather than interesting, so people 
>>> don't
>>> bother.  I don't know whether anyone has actually bothered IRL;  I 
>>> expect
>>> someone has.
>> I never found this anywhere and I did find lots of counter-arguments.
>> Please point me to any resources.
> 
>      Well, it's all absolutely routine, just tedious.
> 
>   -- Step 1:  Use any C compiler of your choice to compile the
>      program to be translated into a machine code of your
>      choice.  The simplest possible m/c code would be good.
>      A simple stack-based code is good.
>   -- Step 2:  At this stage, you have a list of m/c codes that
>      implement your program.  I would simplify the code, at
>      the expense of size, eg by replacing "multiply" by a
>      loop of repeated additions.  But you don't have to, it's
>      just to make step 4 less tedious.
>   -- Step 3:  Replace [eg] the 845th line in your code by a scheme
>      such as
>          state845: [TM quintuples to implement line 845,
>                   see step 4]
>   -- Step 4:  Use a macro facility to replace each m/c code by
>      suitable parametrised TM quintuples.  Eg, given a tape
>      layout such as "...X11111X111E" where numbers are in
>      unary. "X" is a separator, and "E" is end of tape, with
>      the head initially at the "E" [so that the example shows
>      5 and 3 at top of stack], then "add" is implemented by
>      quintuples to (a) scan left to "X", (b) overwrite with
>      "1", (c) scan right to "E", (d) move left one space and
>      write "E".  A "branch" instruction is implemented by a
>      transition to [eg] "state845".  A "load" or "store"
>      instruction is a routine associative copy, as given in
>      many discussions of UTMs.  You have available states
>      such as "state845.123" to implement sub-states of the
>      main states.
> 
> Nothing in the above is difficult, just a matter of programming
> up the replacements for each m/c code and bundling together the
> C compiler and the replacement phases.  I expect there are people
> here who would do it for you, for payment;  but consultancy rates
> in computing are not cheap.
> 

Here is another way that I just derived. We could create Turing machine 
that has the random access of the RAM machine. The length of the 
instructions can vary so that they correspond to the x86 instruction 
set.  https://en.wikipedia.org/wiki/Random-access_machine

This is a variation of the variable length pointer size offer by Kaz
On 8/30/2020 2:41 PM, Kaz Kylheku wrote:
 > Then the strategy is conceivable of allowing a program to calculate
 > until it hits a memory-related resource. Then, at that point,
 > instantiate a new implementation of C which adds one more bit to the
 > width of a pointer relative to the previous implementation (and has
 > the storage to match it).

Each tape element has an unlimited integer address. Instructions have 
fixed length opcodes. Parameters to instructions are unlimited length 
integers. The fixed length opcode is the address location on the tape) 
of the sub-routine that computes the opcode instruction.

When this model of computation is implemented on a physical machine as 
long as the longest unlimited integer is no larger than the machine's 
own hardware allows, we can implement this abstract machine directly.

When the longest integer is larger than the machine's own integer then 
these unlimited integers are implemented as strings of (for example) 
hexadecimal digits that are delimited.

Here is the YACC BNF grammar and LEX regular expressions for the x86 
language mapped to unlimited length addresses and operands.

Instruction
      : INTEGER ":" OpCode
      | INTEGER ":" OpCode Integer
      | INTEGER ":" OpCode Integer "," Integer

HEXDIGIT [a-fA-F-0-9]
INTEGER  {HEXDIGIT}+
OPCODE   HEXDIGIT{4}

Address:OpCode
Address:OpCode Param
Address:OpCode Param, Param




-- 
Copyright 2020 Pete Olcott

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