4 relationer: Funktionel-komplet, Halting-problemet, Turing-ækvivalens, Turing-komplet.
Funktionel-komplet
En komputationel klasse (f.eks. en notation, en maskine eller et programmeringssprog) er funktionel-komplet, hvis alle mulige sandhedstabeller indeholdes af den, bemærk at dette ikke implicerer at systemet er Turing-komplet, da man i mange tilfælde skal bruge et uendeligt program for at skrive en algoritme.
Ny!!: Komputationel klasse og Funktionel-komplet · Se mere »
Halting-problemet
Halting-problemet er et problem indenfor komputabilitetsteori.
Ny!!: Komputationel klasse og Halting-problemet · Se mere »
Turing-ækvivalens
Et Turing-ækvivalent system er et system som er ækvivalent med en Turing-maskine.
Ny!!: Komputationel klasse og Turing-ækvivalens · Se mere »
Turing-komplet
Turing-komplet er en egenskab som en komputationel klasse (f.eks. en notation, en maskine eller et programmeringssprog), som indeholder alle elementer i Turingmaskinens komputationelle gruppe, har, det vil sige at den kan gøre alle de beregninger (komputationer), som en Turing-ækvivalent maskine (f.eks. en normal computer) kan udføre.
Ny!!: Komputationel klasse og Turing-komplet · Se mere »