Let SMTM be Turing Machine, but the commands recorded in which can change to others in some random way (for example, choose with a 50/50 probability the command to move to the right or move to the left), and SM-NTM be non-deterministic Turing Machine with same property (note that NTM non-deterministic in sense of choosing next action, but not the rule, which describes this actions). A difference between a self-modifying Turing machine and TM/NTM: instead of one command for any given situation, or a set of commands in a non-deterministic Turing machine, there is a fuzzy set of commands.

In addition to the question from the title: Is there any papers which describes these sort of theoretical models of computation? In particular, I am interested in the applicability of Rice's theorem for a given computational model. Maybe, there is some connection to quantum computers, NP-hardness, etc.?

The problem that prompted me to this question:

There are neural networks that have an element of non-determinism, where at a certain stage the numbers change by adding random numbers (obtained, for example, from weather observations or observation of the decay of unstable atoms, that is, really random numbers) - do such models have restrictions superimposed on a Turing machine?

  • $\begingroup$ You are looking for probabilistic Turing machines, which are neither deterministic nor non-deterministic. It's a third kind of thing. $\endgroup$ Commented Dec 19, 2021 at 9:27

1 Answer 1


Randomness is not the same as non-determinism -- at least, not the non-determinism that is referred to when people talk about non-deterministic Turing machines.

See Can an algorithm be truly non-deterministic?, Differences and relationships between randomized and nondeterministic algorithms?, https://cstheory.stackexchange.com/q/632/5038, Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?.

There is plenty of study of randomized algorithms and the power of randomness. You can read about BPP, the open question whether BPP = P, etc.

There is plenty of study of non-deterministic algorithms and the power of non-determinism, too. For instance, you can read about the open question whether P = NP.

One common hypothesis/guess/speculation right now is that probably randomness doesn't add much power (maybe P = BPP) but non-determinism is very powerful (probably P != NP).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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