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.

Eksempler på et funktionel-komplet (men ikke Turing-komplet) system er {NOR} og {NOT,OR}. Dog betyder dette ikke at printplader med disse funktioner ikke er Turing-komplette: det er de, fordi det er muligt at danne flip-flops (fordi det er muligt at sende information tilbage i et system, denne egenskab kaldes feedback), som kan danne while-løkker.

Kilder

• Enderton, Herbert (2001), A mathematical introduction to logic (2nd ed.), Boston, MA:Academic Press, ISBN 978-0-12-238452-3.

Spire Denne artikel om matematik er en spire som bør udbygges. Du er velkommen til at hjælpe Wikipedia ved at udvide den.