Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                
Přeskočit na obsah

Rozhodnutelnost

Z Wikipedie, otevřené encyklopedie
(přesměrováno z Nerozhodnutelnost)

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 logického systému

[editovat | editovat zdroj]

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.

Rozhodnutelná teorie

[editovat | editovat zdroj]

Teorie je rozhodnutelná, pokud množina všech formulí v ní dokazatelných je rekurzivní. Není-li teorie rozhodnutelná, nazývá se nerozhodnutelná.

Silně nerozhodnutelná struktura

[editovat | editovat zdroj]

Struktura se nazývá silně nerozhodnutelná, je-li nerozhodnutelná každá teorie, která ji má za model.

Vlastnosti

[editovat | editovat zdroj]

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í:

  • Rozšíření rozhodnutelné teorie o konečně mnoho axiomů v témže jazyce je rozhodnutelné.
  • Rozšíření rozhodnutelné teorie o definice je rozhodnutelné.
  • Teorie, v níž je interpretovatelná nerozhodnutelná teorie, je také nerozhodnutelná.
  • Konzervativní rozšíření nerozhodnutelné teorie je nerozhodnutelné.

O silně nerozhodnutelných strukturách platí:

  • Je-li v nějaké struktuře definovatelná silně nerozhodnutelná struktura, pak je tato struktura také silně nerozhodnutelná.

Dále se často používá:

  • Rekurzivně axiomatizovatelná nerozhodnutelná teorie je neúplná.

Příklady

[editovat | editovat zdroj]

Důsledky nerozhodnutelnosti Robinsonovy aritmetiky

[editovat | editovat zdroj]

Robinsonova aritmetika je nerozhodnutelná teorie. Dokonce každé bezesporné rozšíření Robinsonovy aritmetiky je nerozhodnutelné. Tato dvě tvrzení mají mnoho důsledků:

Rozhodnutelné teorie

[editovat | editovat zdroj]

Následující teorie jsou rozhodnutelné:

Související články

[editovat | editovat zdroj]

Literatura

[editovat | editovat zdroj]