Probabilistic Turing Machines (correct link)

[Eray Ozkural]

Pardon me again, I gave the wrong link. I thought the link I gave included a reference about probabilistic Turing Machines, but it just covered probabilistic FA's.

http://en.wikipedia.org/wiki/Probabilistic_Turing_machine
In computability theory, a probabilistic Turing machine is a non-deterministic Turing machine which randomly chooses between the available transitions at each point according to some probability distribution.

This is the one that is used in AIT. Its indispensability in the theory does make it quite significant. It is likely that Solomonoff was the first to define it, but it would be useful to peruse the various theory of computation textbooks and see if there are any citations about it preceding his use. In Solomonoff memorial conference, a philosopher colleague called it a Solomonoff machine, although I haven't heard that before (I don't think it's a common name, at least not yet). This and the probabilistic complexity classes (like BPP) are usually not discussed much in automata classes, but I think it's one of the most interesting areas in theory of computation.  

If you look at the right hand side box in the wikipedia article, you can see some variations of TM's as well.

Regards,

--
Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philosophy