Stała Chaitina jest przykładem (właściwie rodziną przykładów) liczby nieobliczalnej. reprezentuje prawdopodobieństwo, że losowo wygenerowany program (w pewnym modelu) zatrzyma się. Można ją obliczyć w przybliżeniu, ale nie ma (co jest udowodnione) algorytmu do obliczania jej z dowolną precyzją.
Co sprawia, że liczba jest obliczalna?
Liczba obliczalna to liczba, którą można obliczyć za pomocą skończonego programu komputerowego. Wszystkie liczby, o których kiedykolwiek słyszałeś, takie jak 3, √2, π, e, itp., są obliczalne. Niektóre liczby (np. π) są reprezentowane przez nieskończony ciąg niepowtarzających się cyfr.
Co to znaczy nieobliczalny?
Nieobliczalny jest problemem, dla którego nie ma algorytmu, który mógłby być użyty do jego rozwiązania. Najbardziej znanym przykładem nieobliczalności (lub nierozstrzygalności) jest problem zatrzymania.
Czy istnieją liczby nieobliczalne?
Istnieją nie tylko liczby nieobliczalne,, ale w rzeczywistości są one znacznie bardziej obfite niż liczby obliczalne. Wiele, wiele liczb rzeczywistych to po prostu nieskończone sekwencje pozornie losowych cyfr, bez żadnego wzoru ani specjalnej właściwości. … Jako jeden z takich przykładów rozważ liczbę, której część przed przecinkiem wynosi 0.
Czy liczby rzeczywiste są obliczalne?
Liczba rzeczywista jest obliczalna wtedy i tylko wtedy, gdy zbiór liczb naturalnych, które reprezentuje (kiedy jest zapisywany binarnie i postrzegany jako funkcja charakterystyczna) jest obliczalny. Każdy obliczalnyliczba jest arytmetyczna.
