A machine (physical or virtual) is said to be Turing machine equivalent if it can perform the same tasks as a Turing machine. By their very definition, all programming languages are Turing machine equivalent.

The ideals of a programming language may describe a Turing machine equivalent, but there is no implementation yet which is. Nor will there ever be - the Turing machine has (potentially) infinite memory.

The definition of P-class problems and NP-class problems are the primary use for the idea of Turing machine equivalents.

Log in or register to write something here or to contact authors.

Sign up

Need help? accounthelp@everything2.com