Funktionel-komplet

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

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 algorithme.

Eksempeler på et funktionelt-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 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[redigér | redigér wikikode]

  • Enderton, Herbert (2001), A mathematical introduction to logic (2nd ed.), Boston, MA:Academic Press, ISBN 978-0-12-238452-3.
Artikelstump Stub
Denne artikel er kun påbegyndt. Hvis du ved mere om emnet, kan du hjælpe Wikipedia ved at udvide den.