Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Transforming "C" into a Turing equivalent language 001 [ TM equivalent computations ]
3 views
Skip to first unread message
olcott
Sep 1, 2020, 4:09:08 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 traces between the abstract
model and its concrete implementation for all computations not requiring
more memory than is available.
This would guarantee that the execution of an x86 program on an input
would be equivalent to the execution of a Turing machine on equivalent
input for all x86 programs that complete executing and halt.
The Church-Turing thesis makes no such guarantee:
https://plato.stanford.edu/entries/church-turing/
--
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 traces between the abstract
model and its concrete implementation for all computations not requiring
more memory than is available.
This would guarantee that the execution of an x86 program on an input
would be equivalent to the execution of a Turing machine on equivalent
input for all x86 programs that complete executing and halt.
The Church-Turing thesis makes no such guarantee:
https://plato.stanford.edu/entries/church-turing/
--
Copyright 2020 Pete Olcott
0 new messages