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.