AFAIK, numery obliczalne są liczbami, których i-ten indeks może być zwrócony przez maszynę Turinga. Tak więc liczba niecałkowita byłaby czymś w rodzaju liczby, której decymalne punkty zostaną ustalone, jeśli jakiś inny program zatrzyma się na jakimś innym wejściu itd. Ale znowu PI jest liczbą rzeczywistą, której nie można wyliczyć za pomocą T.M. a zatem nie można obliczyć? Więc która szkoła myślenia jest poprawna?Czy PI jest numerem obliczalnym?
Tak, π jest obliczalne. Istnieje kilka równoważnych definicji obliczalnych, ale najbardziej przydatna jest tutaj ta, którą podałeś powyżej: rzeczywistą liczbę r można obliczyć, jeśli istnieje algorytm znajdowania jej cyfr n. Here jest takim algorytmem.
Twój ostatni argument nie jest dźwięk; pomyliłeś definicję "można znaleźć n th cyfra" z "można wyliczyć wszystkie cyfry". Ta ostatnia definicja nie jest użyteczna: wyklucza wszystkie irracjonalne i wiele racjonalnych rozwiązań!
Ciekawostką jest fakt, że liczby obliczalne są w rzeczywistości policzalne, ponieważ możemy numerować maszyny Turinga, które je produkują. Stąd prawie nie ma obliczeń rzeczywistych.
Myślę, że masz na myśli prawie wszystkie liczby rzeczywiste * nie * obliczalne, ponieważ zestaw maszyn Turinga jest policzalny. –
@ larsmans: tak, oczywiście =) – katrielalex
Dzięki za wyczyszczenie tego! Twoje zdrowie! –
Nie jestem całkiem pewien, co masz na myśli przez "PI to liczba rzeczywista, której nie można wyliczyć za pomocą T.M.". Tak, rzeczywiste liczby nie są przeliczalne, ale nie widzę, jak to wpływa, czy PI jest obliczalne. '4' jest również liczbą rzeczywistą, ale to nie znaczy, że nie jest obliczalne. – sepp2k
Um, chodziło mi o to, myślałem, że potrzeba nieskończenie długiej Maszyny Turinga do obliczenia PI, ponieważ sam PI jest nieskończenie długi. –
@Gaurav: przez ten argument, czy potrzeba nieskończenie długiej maszyny Turinga do obliczenia "1/3", skoro "1/3 = 0.333333 ..." jest nieskończenie długie? – katrielalex