Samopoužitelnost
Vlastní použitelnost v teorii algoritmů je vlastnost algoritmu úspěšně dokončit na datech, která jsou formálním záznamem stejného algoritmu.
Problém rozpoznávání vlastní použitelnosti je algoritmicky neřešitelný a scvrkává se na nalezení algoritmu, který umožňuje v konečném počtu kroků ve formálním zápisu nějakého algoritmu zjistit, zda je nebo není samoaplikovatelný. Přestože je tento problém poněkud umělý a není nezávislým předmětem zájmu, často se používá k prokázání neřešitelnosti jiných, složitějších problémů. Obecná metoda pro takové inference je taková, že z předpokladu existence algoritmu, který řeší určitý problém, se odvozuje existence algoritmu, který řeší problém rozpoznání vlastní použitelnosti.
Důkaz algoritmické nerozhodnutelnosti
Důkaz kontradikcí . Předpokládejme, že existuje algoritmus, který uznává vlastní použitelnost. Na základě Turingovy teze existuje také Turingův stroj , který tento algoritmus implementuje. Označme takový stroj jako . Na jeho pásku se nějakým způsobem zadá zakódovaný program jiného Turingova stroje a po práci se zadaná data zpracují do slova , pokud byl původní program samoaplikovatelný, nebo do slova , pokud samopoužitelný nebyl.
Ve druhém kroku stroj mírně upravíme tak, aby stále zpracovával programy, které nejsou samoaplikovatelné v , a smyčky na samopoužitelných programech , to znamená, že je pro ně neaplikovatelné. Je velmi snadné provést takovou transformaci - po napsání slova stroj nedokončí svou práci, ale pokračuje v nekonečném zápisu na pásku. Označme toto auto jako . Existence takového stroje vede k rozporu, protože nemůže být ani samopoužitelný, ani nepoužitelný. Je-li skutečně použitelný, pak je použitelný na vlastní zápis. Ale podle konstrukce stroje to jen naznačuje, že není samopoužitelný. Pokud to není samoaplikovatelné, pak je konstrukčně použitelné pro svůj vlastní záznam, protože je použitelné pro jakýkoli záznam o neaplikovatelném stroji. Ale to jen znamená, že je to samoúčelné. Na základě toho je učiněn závěr o nemožnosti sestrojit stroj , od té doby by se z něj dalo snadno dostat .
Literatura
- V. I. IGOSHIN Matematická logika a teorie algoritmů. - M .: Akademie, 2004. - S. 369-370. — 448 s. - 5100 výtisků. — ISBN 5-7695-1363-2 .
- A. L. Semjonov. Samostatně použitelné programy // Matematika textů . - 2002. - 16 s. - 3000 výtisků. — ISBN 5-94057-006-2 .
- E. M. Ivanov. Gödelův argument // K problému "vyčíslitelnosti" funkce vědomí .
- Michiel Hazewinkel. Nerozhodnutelnost // Encyklopedie matematiky . - Berlin: Springer Netherland, 2002. - ISBN 1-4020-0609-8 . (Angličtina)
- Arto Salomaa. 4.3 Rekurzní teorém a základní výsledky nerozhodnutelnosti // Výpočet a automaty . - Cambridge University Press, 1985. - V. 25. - S. 90. - 284 s. — ISBN 9780521302456 . (Angličtina)