beräkningsbara tal

(computable numbers) – tal som kan räknas fram med en algoritm, alltså alla tal som kan räknas fram på ett sätt som kan beskrivas i ett ändligt antal steg. (Talen kan däremot ha oändligt många siffror, så beräkningen kan i teorin pågå i all evighet, om man inte avrundar talen.) De be­räk­nings­bara talen är en del av de reella talen, men de flesta reella tal är troligen inte beräkningsbara. Det finns delade meningar om det. En viktig skillnad mellan reella tal och beräkningsbara tal är att de beräkningsbara talen är uppräkneliga (numrerbara). De reella talen är däremot inte uppräkneliga, så det verkar rimligt att de beräkningsbara talen bara är en delmängd av de reella talen. – Läs också om Alan Turing och stopproblemet samt om talet omega.

[matematik] [ändrad 6 juni 2017]