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.