Teorie vyčíslitelnosti: Porovnání verzí

Smazaný obsah Přidaný obsah

V textu

Verze z 29. 10. 2007, 02:26

Teorie vyčíslitelnosti zkoumá hranice algoritmické konstrukce množin. Pro modelování využívá například Turingův stroj, částečně rekurzivní funkce a intuicionistickou logiku.

Nelze zkonstruovat algoritmus, který by pro obecný program ověřil jeho konečnost (tzv. problém zastavení).

Ke každému algoritmu existuje ekvivalentní Turingův stroj (tzv. Church-Turingova teze).

@@ Řádek 21: / Řádek 21: @@
 [[fa:نظریه محاسبه‌پذیری]]
 [[fr:Calculabilité]]
+[[he:חישוביות]]
+[[hr:Teorija izračunljivosti (računarstvo)]]
 [[it:Teoria della calcolabilità]]
 [[ja:計算可能性理論]]
@@ Řádek 26: / Řádek 28: @@
 [[nl:Berekenbaarheid]]
 [[pl:Teoria obliczalności]]
+[[pt:Computabilidade]]
 [[ru:Теория вычислимости]]
 [[simple:Computability theory]]