Turing-ækvivalens
Udseende
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
[redigér | rediger kildetekst]- John Hopcroft and Jeffrey Ullman (1979). Introduction to Automata Theory, Languages and Computation (1st ed.). Addison–Wesley, Reading Mass. ISBN 0-201-02988-X.