Teoria obliczalnosci

Klasyfikacja zbiorów nieobliczalnych według liczby naprzemiennych kwantyfikatorów w ich definicji logicznej.

Język, dla którego istnieje maszyna Turinga akceptująca wszystkie jego słowa, lecz mogąca nie zatrzymać się dla słów spoza niego.

Język, dla którego istnieje maszyna Turinga zawsze zatrzymująca się i rozstrzygająca przynależność słowa.

Własność języka, dla którego istnieje maszyna Turinga zatrzymująca się i poprawnie odpowiadająca tak/nie dla każdego wejścia.

Abstrakcyjny model obliczeniowy z nieskończoną taśmą i głowicą, definiujący granicę tego, co algorytmicznie obliczalne.

Maszyna Turinga symulująca działanie dowolnej innej maszyny zakodowanej na jej wejściu wraz z danymi.

Własność problemu, dla którego nie istnieje algorytm rozstrzygający go dla wszystkich wejść.

Problem doboru ciągu par słów dających po sklejeniu identyczne łańcuchy; klasyczny problem nierozstrzygalny.

Problem decyzyjny, dla którego nie istnieje algorytm dający poprawną odpowiedź dla każdego wejścia.

Problem rozstrzygnięcia, czy dany program zatrzyma się dla danego wejścia; dowodliwie nierozstrzygalny.

Twierdzenie głoszące, że każda nietrywialna własność semantyczna języków rozpoznawanych przez maszyny Turinga jest nierozstrzygalna.

Własność funkcji lub problemu polegająca na istnieniu efektywnej procedury (algorytmu) zwracającej wynik.

Twierdzenie głoszące, że każda funkcja efektywnie obliczalna jest obliczalna przez maszynę Turinga.

Klasa równoważności zbiorów o tej samej trudności obliczeniowej względem redukowalności Turinga.

Hipotetyczne urządzenie rozstrzygające pewien problem w jednym kroku, dołączone do maszyny w celu badania względnej obliczalności.

Technika dowodowa konstruująca obiekt różniący się od każdego elementu listy, używana do wykazania nieprzeliczalności i nierozstrzygalności.

Funkcja obliczalna mogąca być niezdefiniowana dla niektórych argumentów, gdy obliczenie nie kończy się.

Funkcja budowana z funkcji bazowych przez złożenie i rekursję pierwotną, zawsze całkowita, lecz węższa od wszystkich funkcji obliczalnych.

Funkcja obliczalna zdefiniowana przez rekursję pierwotną, minimalizację i funkcje bazowe; klasa równoważna funkcjom obliczalnym Turinga.

Twierdzenie zapewniające, że maszyna Turinga może uzyskać własny opis i użyć go w obliczeniach.