Re: Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations]

From	Keith Thompson <Keith.S.Thompson+u@gmail.com>
Newsgroups	comp.theory, comp.lang.c, comp.lang.c++, comp.ai.philosophy
Subject	Re: Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations]
Followup-To	comp.theory, comp.lang.c, comp.ai.philosophy
Date	2020-09-02 23:22 -0700
Organization	None to speak of
Message-ID	<87mu27z8eo.fsf@nosuchdomain.example.com> (permalink)
References	<I5mdnZ4oyLTc983CnZ2dnUU7-a3NnZ2d@giganews.com>

Cross-posted to 4 groups.

Followups directed to: comp.theory, comp.lang.c, comp.ai.philosophy

Show all headers | View raw

olcott <NoOne@NoWhere.com> writes:
> When we map "C" to a Turing equivalent abstract model of compuation
> "C" becomes Turing equivalent.
>
> Mapping x86 programs to a Turing equivalent abstract model
> The following abstract machine maps the x86 language to machines with
> a fixed pointer size of the largest unlimited integer address that is
> actually needed by the computation.
>
> 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
>
> All Intel x86/x64 programs that map to the above abstract model of
> computation would be provably Turing equivalent computations. This
> means that they would always produce equivalent output for equivalent
> input and have the same halting behavior.

Since you don't even mention C++, please don't cross-post this to
comp.lang.c++.

This:
    HEXDIGIT [a-fA-F-0-9]
should be:
    HEXDIGIT [a-fA-F0-9]

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

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

Thread

Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations] olcott <NoOne@NoWhere.com> - 2020-09-02 23:00 -0500
  Re: Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations] Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-09-02 23:22 -0700
    Re: Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations] olcott <NoOne@NoWhere.com> - 2020-09-03 09:49 -0500
      Re: Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations] Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-09-03 10:49 -0700
        Re: Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations] olcott <NoOne@NoWhere.com> - 2020-09-03 12:52 -0500
    Re: Transforming "C" into a Turing equivalent language 007 [Turing equivalent x86 computations] olcott <NoOne@NoWhere.com> - 2020-09-03 09:51 -0500

csiph-web