Berechenbare Zahlen
Eine Zahl heißt genau dann berechenbar, wenn es eine Turing-Maschine gibt, die für jedes eine Zahl ausgibt, so dass gilt, die also die Zahl beliebig genau approximieren kann.Alle natürlichen Zahlen, rationalen Zahlen und algebraischen Zahlen sind berechenbar, aber auch einige transzendente Zahlen wie z.B. die Kreiszahl oder Eulersche Zahl .
Da es nur abzählbar viele Turing-Maschinen, aber überabzählbar viele reelle Zahlen gibt, sind die berechenbaren Zahlen eine echte Teilmenge von .