Internal Turing Machines

Details Internal Turing Machines Internal Turing Machines

2004-07-23

arxiv.org/abs/math-ph/0407056v2

Physics

Mathematical Physics

clarified the Halting problem

Scientific paper

Using nonstandard analysis, we will extend the classical Turing machines into the internal Turing machines. The internal Turing machines have the capability to work with infinite ($*$-finite) number of bits while keeping the finite combinatoric structures of the classical Turing machines. We will show the following. The internal deterministic Turing machines can do in $*$-polynomial time what a classical deterministic Turing machine can do in an arbitrary finite amount of time. Given an element of $\in HALT$ (more precisely, the $*$-embedding of $HALT$), there is an internal deterministic Turing machine which will take $$ as input and halt in the $"yes"$ state. The language ${}^*Halt$ can not be decided by the internal deterministic Turing machines. The internal deterministic Turing machines can be viewed as the asymptotic behavior of finite precision approximation to real number computations. It is possible to use the internal probabilistic Turing machines to simulate finite state quantum mechanics with infinite precision. This simulation suggests that no information can be transmitted instantaneously and at the same time, the Turing machine model can simulate instantaneous collapse of the wave function. The internal deterministic Turing machines are powerful, but if $P \neq NP$, then there are internal problems which the internal deterministic Turing machines can solve but not in $*$-polynomial time.

Affiliated with

Also associated with

No associations

Rating

Internal Turing Machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Internal Turing Machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Internal Turing Machines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-397842