matematický pojem z oblasti matematické logiky From Wikipedia, the free encyclopedia
Rozhodnutelnost (A je - není větší, než B, formule W je pravdivá – nepravdivá, a je - není prvkem množiny Y, Turingův stroj zastaví - nezastaví...) je vlastnost exaktního světa (matematika, geometrie, Turingův stroj, exaktní hry např. šachy,...), v němž veškeré entity mají exaktní interpretaci. Rozhodnutelnost nelze instalovat v mlze vágnosti přirozeného světa vágní, emocionální a subjektivní lidské psýchy, používající přirozený jazyk s vágní (vnitřní vágnost), emocionální a subjektivní interpretací měnící se od člověka k člověku a u každého z nich v čase, které se říká konotace. Nemůže proto existovat např. logika postavená nad přirozeným jazykem, může existovat pouze formální logika postavená nad umělým formálním jazykem, který má z principu exaktní (s nulovou vnitřní vágností) interpretaci.
Rozhodnutelnost je matematický pojem z oblasti matematické logiky. Vyjadřuje, zda existuje konečný algoritmus, který pro každou formuli určí, zda je v dané teorii dokazatelná nebo není. Teorie, pro niž takový algoritmus existuje, se nazývá rozhodnutelná, v opačném případě pak nerozhodnutelná. Problematika rozhodnutelnosti úzce souvisí s Gödelovými větami o neúplnosti.
Teorie je rozhodnutelná, pokud množina všech formulí v ní dokazatelných je rekurzivní. Není-li teorie rozhodnutelná, nazývá se nerozhodnutelná.
Struktura se nazývá silně nerozhodnutelná, je-li nerozhodnutelná každá teorie, která ji má za model.
Rozhodnutelnost či nerozhodnutelnost se přenáší mezi teoriemi, mezi nimiž je určitý vztah. Nejpoužívanější tvrzení, která o tomto hovoří, jsou následující:
O silně nerozhodnutelných strukturách platí:
Dále se často používá:
Robinsonova aritmetika je nerozhodnutelná teorie. Dokonce každé bezesporné rozšíření Robinsonovy aritmetiky je nerozhodnutelné. Tato dvě tvrzení mají mnoho důsledků:
Následující teorie jsou rozhodnutelné:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.