Three aspects of decidability

Abstrakt

W artykule dokonano krótkiej analizy pojęcia rozstrzygalności w trzech kolejnych okresach jej rozwoju. Pierwszy okres obejmuje lata przed rokiem 1930, w których problemy rozstrzygalności uzyskały właściwe znaczenie głównie za sprawą badań związanych z programem Hilberta. Okres drugi obejmuje lata trzydzieste i czterdzieste. Wykorzystując rozmaite podejścia, wypracowano wówczas ścisłe, matematyczne pojęcie obliczalności, co umożliwiło przyjęcie równie precyzyjnej definicji rozstrzygalności. Z kolei okres trzeci rozpoczyna się mniej więcej od początku lat sześćdziesiątych, kiedy to w związku z procedurami możliwymi do realnego urzeczywistnienia pojawiła się refleksja nad praktyczną rozstrzygalnością.