Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have currently started a new research line aiming to prove a mapping between a 2-symbol Turing machine and the one dimensional Ising model. The connection is seen by recognizing that a set of symbols on the tape of the machine is indeed a configuration of a one-dimensional Ising model.

The relevance of this connection relies on the fact that a limit on the entropy for information has been conjectured by Rolf Landauer in the '60. A mapping between a Turing machine and the Ising model can make this conjecture a theorem.

My question here is what are the main references on Turing machines, probabilistic Turing machine and so on? Does it exist any standard, research level, literature to consider?

Especially for probabilistic Turing machines, does it exist some result making them equivalent to a deterministic Turing machine and, in any case, there exists a theorem stating they can compute anything a deterministic Turing machine can?

Thanks.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

Of course there is a huge literature on Turing machines, probabilistic Turing machines and so on, including thousands of research articles and hundreds of books.

So let me consider only the final question, Are probabilistic Turing machines equally as powerful computationally as deterministic Turing machines?

There are several ways to understand what is meant by "probabilistic Turing machine", and the answer to this question depends on the particular details. Let us imagine that we have equipped a standard Turing machine with a random-bit source, so that the computation can have access to random bits for whatever purpose.

One the one hand, we could say that a function $f$ is computable by such a probabilistic machine if there is finite program whose operation on input $x$ invariably produces output $f(x)$. That is, even though the algorithm involves randomness, we insist nevertheless that it computes the function correctly regardless of which random branch of computation is followed. Similarly, a set is decidable by such a probabilistic machine if the characteristic function of the set is computable. The point, now, is that this understanding of the probabilistic machines does not change the class of computable functions or the class of decidable sets; they are equally powerful: a function is computable by a classical Turing machine if and only if it is computable in this sense by a probabalistic Turing machine. The reason is simply that for any probabalistic algorithm, we can design a classical algorithm that simply simulates the tree of all possible probabilistic courses of computation. Whenever the probabilistic algorithm samples the random bit source, then our classical algorithm will simply create two copies of the computation so far, imagining first that the bit was one and secondly that the bit was zero, and see what happens in both cases. Eventually, we will find a branch of the computation giving an output, and this output must be the correct $f(x)$, since the probabilistic algorithm computed $f(x)$ correctly on all its branches.

Thus, the probabilistic machines have more to do with increasing the speed of the computation rather than with increasing the fundamental computational power of the machines. Thus, they are associated more with complexity theory than with computability theory.

On the other hand, with the probabilistic machines, it is easy to design algorithms that do not always give the same output regardless of the random branch of computation that is followed. In this case, it is clear that the machines can write out infinite strings on the tape that cannot be written by any deterministic computable procedure. Indeed, if the algorithm simply copies the random source to the output tape, it essentially creates a random element of Cantor space. With probability one, this binary sequence will not be deterministically computable, simply because there are infinitely many independent chances for it to deviate from any given real.

But one could object that this is not really a concept of computation, since it isn't really repeatable.

Another somewhat more refined concept would be to have a probabilistic concept for the output of the machines. That is, let us only insist that there is a certain probability of a correct answer. In order to be useful, one would ordinarily want this probability to exceed .5 by some known amount. Thus, for this concept, we say that a set $A$ is decidable by the probabilistic machines if there is an algorithm which on input $x$ has a probability exceeding .5 of answering correctly whether or not $x\in A$. This case, however, is similar to the first case I mention above, since given any such probabilistic algorithm, we may design a classical algorithm that runs all the branches of computation, and checks whether or not the majority of them say yes or say no. Thus, a set is decidable by a probabilistic machine in this sense if and only if it is decidable classically.

But again, the classical algorithm here will take far longer than the probabilistic machine, and so the topic belongs to complexity theory rather than computability theory.

Finally, let me mention that you will likely be interested in quantum Turing machines, which are like probabilistic Turing machines, except that they also allow for quantum-mechanical constructive and desctructive interference between the random branches of computation.

share|improve this answer
    
Thanks a lot for this beautiful answer. You have clarified me a lot. Quantum information is not my concern for the moment as, for now, I am interested about physical limits of classical computation. –  Jon May 30 '12 at 12:57
1  
The practioners of quantum Turing machines are so far along in that direction that they often regard the probabilistic Turing machines as "classical". –  Joel David Hamkins May 30 '12 at 13:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.