istnienia dowolnie długich bloków tej samej cyfry).
Skończone fragmenty wartości funkcji pracowitego bobra są obliczalne, choć sama funkcja nie jest obliczalna.
Hipoteza Churcha-Turinga
Teza Churcha głosi, że każda funkcja obliczalna w intuicyjnym sensie efektywnej procedury jest obliczalna w sensie formalnym (np. przez maszynę Turinga). Ze względu na nieformalny charakter pojęcia „efektywnej procedury” tezy tej nie można ściśle udowodnić.
Na jej rzecz przemawia m.in. równoważność wielu niezależnie zaproponowanych modeli obliczeń oraz brak ogólnie akceptowanego silniejszego modelu odpowiadającego intuicyjnemu pojęciu obliczalności.
Funkcje nieobliczalne i zagadnienia nierozwiązywalne Ponieważ każda funkcja obliczalna ma skończony opis, istnieje przeliczalnie wiele funkcji obliczalnych.
Z kolei zbiór wszystkich funkcji z liczb naturalnych w liczby naturalne jest nieprzeliczalny, a więc „większość” takich funkcji jest nieobliczalna.
Klasycznym przykładem problemu nierozstrzygalnego jest Problem stopu.