Zagadnienie rozstrzygalności postawione przez Davida Hilberta doprowadziło do wykazania przez Turinga i Churcha, że nie istnieje ogólna efektywna procedura rozstrzygająca prawdziwość wszystkich zdań arytmetyki.
Rozszerzenia obliczalności Pojęcie obliczalności można zrelatywizować względem zbioru (lub funkcji ) poprzez rozważanie maszyny Turinga z wyrocznią. Otrzymane w ten sposób funkcje nazywa się A-obliczalnymi (odpowiednio f-obliczalnymi).
Badania nad rozszerzeniami klasycznej obliczalności obejmują m.in. hiperobliczalność oraz uogólnione teorie rekurencji.
Zobacz też
Teoria obliczalności
Przypisy
Obliczalna Kategoria:Teoria obliczeń