Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

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

19 views
Skip to first unread message

olcott

unread,
Sep 3, 2020, 12:00:29 AM9/3/20
to
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.


--
Copyright 2020 Pete Olcott

Keith Thompson

unread,
Sep 3, 2020, 2:22:57 AM9/3/20
to
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.T...@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */
0 new messages