Turing-ækvivalens

Et Turing-ækvivalent system er et system som er ækvivalent med en Turing-maskine. Altså et system som indeholder de præcis samme elementer i sin komputationelle klasse som Turing-maskinen gør.

At et system er Turing-komplet implicerer ikke at det også er Turing-ækvivalent, f.eks. er en relativistisk computer ikke Turing-ækvivalent (da den f.eks. kan løse halting-problemet), men den er Turing-komplet.

Kilder

• John Hopcroft and Jeffrey Ullman (1979). Introduction to Automata Theory, Languages and Computation (1st ed.). Addison–Wesley, Reading Mass. ISBN 0-201-02988-X.