Nr 01 · Słownik · Teoria informatyki · Matematyka dyskretna i teoria obliczeń

Teoria obliczalnosci

20 pojęć w 8 podgrupach, z prostymi definicjami i źródłami.

Hierarchie · 1

  • 01hierarchia arytmetycznaKlasyfikacja zbiorów nieobliczalnych według liczby naprzemiennych kwantyfikatorów w ich definicji logicznej.

Klasy jezykow · 3

  • 01język rekurencyjnie przeliczalnyr.e.; język semirozstrzygalnyJęzyk, dla którego istnieje maszyna Turinga akceptująca wszystkie jego słowa, lecz mogąca nie zatrzymać się dla słów spoza niego.
  • 02język rekurencyjnyjęzyk rozstrzygalnyJęzyk, dla którego istnieje maszyna Turinga zawsze zatrzymująca się i rozstrzygająca przynależność słowa.
  • 03rozstrzygalnośćWłasność języka, dla którego istnieje maszyna Turinga zatrzymująca się i poprawnie odpowiadająca tak/nie dla każdego wejścia.

Modele obliczen · 2

  • 01maszyna TuringaAbstrakcyjny model obliczeniowy z nieskończoną taśmą i głowicą, definiujący granicę tego, co algorytmicznie obliczalne.
  • 02uniwersalna maszyna TuringaMaszyna Turinga symulująca działanie dowolnej innej maszyny zakodowanej na jej wejściu wraz z danymi.

Nierozstrzygalnosc · 5

  • 01nierozstrzygalnośćWłasność problemu, dla którego nie istnieje algorytm rozstrzygający go dla wszystkich wejść.
  • 02problem korespondencji PostaPCPProblem doboru ciągu par słów dających po sklejeniu identyczne łańcuchy; klasyczny problem nierozstrzygalny.
  • 03problem nierozstrzygalnyProblem decyzyjny, dla którego nie istnieje algorytm dający poprawną odpowiedź dla każdego wejścia.
  • 04problem stopuProblem rozstrzygnięcia, czy dany program zatrzyma się dla danego wejścia; dowodliwie nierozstrzygalny.
  • 05twierdzenie Rice'aTwierdzenie głoszące, że każda nietrywialna własność semantyczna języków rozpoznawanych przez maszyny Turinga jest nierozstrzygalna.

Podstawy obliczalnosci · 2

  • 01obliczalnośćWłasność funkcji lub problemu polegająca na istnieniu efektywnej procedury (algorytmu) zwracającej wynik.
  • 02teza Churcha-TuringaTwierdzenie głoszące, że każda funkcja efektywnie obliczalna jest obliczalna przez maszynę Turinga.

Redukowalnosc · 2

  • 01stopień Turingastopień nierozstrzygalnościKlasa równoważności zbiorów o tej samej trudności obliczeniowej względem redukowalności Turinga.
  • 02wyroczniamaszyna z wyroczniąHipotetyczne urządzenie rozstrzygające pewien problem w jednym kroku, dołączone do maszyny w celu badania względnej obliczalności.

Techniki dowodowe · 1

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

Teoria rekursji · 4

  • 01funkcja częściowo rekurencyjnafunkcja częściowa obliczalnaFunkcja obliczalna mogąca być niezdefiniowana dla niektórych argumentów, gdy obliczenie nie kończy się.
  • 02funkcja rekurencji pierwotnejfunkcja pierwotnie rekurencyjnaFunkcja budowana z funkcji bazowych przez złożenie i rekursję pierwotną, zawsze całkowita, lecz węższa od wszystkich funkcji obliczalnych.
  • 03funkcja rekurencyjnafunkcja μ-rekurencyjnaFunkcja obliczalna zdefiniowana przez rekursję pierwotną, minimalizację i funkcje bazowe; klasa równoważna funkcjom obliczalnym Turinga.
  • 04twierdzenie o rekursjiTwierdzenie zapewniające, że maszyna Turinga może uzyskać własny opis i użyć go w obliczeniach.

Pozostałe grupy — Matematyka dyskretna i teoria obliczeń

Grupa pojęć · Matematyka dyskretna i teoria obliczeń20 haseł