Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Transforming "C" into a Turing equivalent language 001 [x86 based UTM]
9 views
Skip to first unread message
olcott
Sep 1, 2020, 12:10:57 PM9/1/20
to
Turing equivalent x86 computations are defined as:
(a) An x86 program can be translated into an abstract model of
computation that is provably equivalent to a Turing machine.
(b) The abstract model of computation can be concretely implemented on
physical hardware.
(c) All computations performed on the concrete implementation have an
identical (state-change-by-state-change and
tape-head-move-by-tape-head-move) execution trace between the abstract
model and its concrete implementation for all computations not requiring
more memory than is available.
Applying this same reasoning to my x86-UTM shows that many computations
performed by the x86 based UTM are equivalent to computations on an
actual UTM.
Besides memory allocation from the heap the x86-UTM provides a virtual
machine instruction allowing any UTM to execute another UTM in
debug-step mode. This recursive invocation can be to an arbitrary
recursive depth.
UTMs can be written in Microsoft "C". The resulting COFF object file can
be directly executed by the x86-UTM. All global data must be
initialized. All global data references in the code section are patched
to refer to their offset in the COFF data section. Execution uses the
flat 32-bit model.
The x86 based UTM will be posted to a code repository as open source
with a very permissive license.
--
Copyright 2020 Pete Olcott
(a) An x86 program can be translated into an abstract model of
computation that is provably equivalent to a Turing machine.
(b) The abstract model of computation can be concretely implemented on
physical hardware.
(c) All computations performed on the concrete implementation have an
identical (state-change-by-state-change and
tape-head-move-by-tape-head-move) execution trace between the abstract
model and its concrete implementation for all computations not requiring
more memory than is available.
Applying this same reasoning to my x86-UTM shows that many computations
performed by the x86 based UTM are equivalent to computations on an
actual UTM.
Besides memory allocation from the heap the x86-UTM provides a virtual
machine instruction allowing any UTM to execute another UTM in
debug-step mode. This recursive invocation can be to an arbitrary
recursive depth.
UTMs can be written in Microsoft "C". The resulting COFF object file can
be directly executed by the x86-UTM. All global data must be
initialized. All global data references in the code section are patched
to refer to their offset in the COFF data section. Execution uses the
flat 32-bit model.
The x86 based UTM will be posted to a code repository as open source
with a very permissive license.
--
Copyright 2020 Pete Olcott
olcott
Sep 1, 2020, 12:51:58 PM9/1/20
to
On 9/1/2020 11:10 AM, olcott wrote:
> Turing equivalent x86 computations are defined as:
> (a) An x86 program can be translated into an abstract model of
> computation that is provably equivalent to a Turing machine.
>
> (b) The abstract model of computation can be concretely implemented on
> physical hardware.
>
> (c) All computations performed on the concrete implementation have an
> identical (state-change-by-state-change and
> tape-head-move-by-tape-head-move) execution trace between the abstract
> model and its concrete implementation for all computations not requiring
> more memory than is available.
>
> Applying this same reasoning to my x86-UTM shows that many computations
> performed by the x86 based UTM are equivalent to computations on an
> actual UTM.
>
> Besides memory allocation from the heap the x86-UTM provides a virtual
> machine instruction allowing any UTM to execute another UTM in
> debug-step mode. This recursive invocation can be to an arbitrary
> recursive depth.
>
> UTMs can be written in Microsoft "C". The resulting COFF object file can
> be directly executed by the x86-UTM. All global data must be
> initialized.
No library functions can be called. Uninitialized global data and
> Turing equivalent x86 computations are defined as:
> (a) An x86 program can be translated into an abstract model of
> computation that is provably equivalent to a Turing machine.
>
> (b) The abstract model of computation can be concretely implemented on
> physical hardware.
>
> (c) All computations performed on the concrete implementation have an
> identical (state-change-by-state-change and
> tape-head-move-by-tape-head-move) execution trace between the abstract
> model and its concrete implementation for all computations not requiring
> more memory than is available.
>
> Applying this same reasoning to my x86-UTM shows that many computations
> performed by the x86 based UTM are equivalent to computations on an
> actual UTM.
>
> Besides memory allocation from the heap the x86-UTM provides a virtual
> machine instruction allowing any UTM to execute another UTM in
> debug-step mode. This recursive invocation can be to an arbitrary
> recursive depth.
>
> UTMs can be written in Microsoft "C". The resulting COFF object file can
> be directly executed by the x86-UTM. All global data must be
> initialized.
library function calls produce an error message.
0 new messages