oraz Roger Penrose twierdzą, że ludzki umysł jest przykładem kwantowego hiperkomputera, lecz nie ma na to żadnych naukowych dowodów.
Nierozwiązywalne problemy Istnieją funkcje oraz problemy, które są niemożliwe do obliczenia za pomocą maszyny Turinga. Dla takich problemów, zawsze istnieje zestaw danych, dla których dowolny zaproponowany algorytm nie zatrzyma się lub da błędną odpowiedź. W przypadku funkcji, operując na liczbach naturalnych, mogą one produkować niezwykle duże wyniki. Jedną z najsłynniejszych takich funkcji jest Busy Beaver. Określa ona maksymalną ilość pracy, jaką może wykonać maszyna Turinga o zadanej z góry liczbie stanów n (argument funkcji), przy czym nie uwzględniamy tutaj maszyn działających w nieskończoność. Naukowcy potrafią podać jedynie prawidłowy wynik dla pierwszych czterech liczb naturalnych, natomiast dla kolejnych znane jest tylko dolne oszacowanie. Funkcja ta ma wiele powiązań z problemem stopu, który także jest nierozwiązywalny.
Zobacz też kompletność Turinga teoria obliczeń złożoność obliczeniowa
Przypisy
Bibliografia
Linki zewnętrzne [dostęp 2026-01-16]. Church thesis , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-10-05].
Church’s thesis , Routledge Encyclopedia of Philosophy, rep.routledge.com [dostęp 2023-05-10].
Kategoria:Teoria obliczeń Kategoria:Algorytmika