Hlavní stránka > Výsledky hledání: keywords:"first-order theories|incompleteness theorems and Berry's paradox"
Hledej:
Tipy pro vyhledávaní :: Rozšířené hledání
Hledej ve sbírkách:
Seřadit podle: Zobrazit výsledky: Výstupní formát:
Národní úložiště šedé literatury Nalezeno 1 záznamů.  Hledání trvalo 0.01 vteřin. 
The incompleteness theorems and Berry's paradox
 Grego, Maroš ; Krajíček, Jan (vedoucí práce) ; Kompatscher, Michael (oponent)
Tahle práce je věnovaná formální prezentaci alternativního důkazu Gödelovy první věty o neúplnosti, založeném na Berryho paradoxu ("nejmeší číslo, které nelze defino- vat méně než 57 znaky", přičemž tahle definice má méně znaků a definuje tohle číslo). Použitý přístup byl navržen v článku G. Chaitina. Definujeme Kolmogorovovu složitost přirozeného čísla m jako binární délku nejmešího programu pro univerzální Turingův stroj, který na vstupu 0 vrátí číslo m. Pomocí formálního argumentu inspirovaného Berryho paradoxem ukážeme nedokazatelnost tvrzení, že číslo n je dolní mezí pro Kol- mogorovovu složitost čísla m v jakémkoliv konzistentím rekurzivně axiomatizovatelném rozšíření Robinsonovy aritmetiky. Jednoduchý početní argument ale ukáže, že pro všechna n je tohle tvrzení pravdivé pro všechna až na konečně mnoho m. To je využito k důkazu první věty o neúplnosti. Jiný způsob (pocházející od G. S. Boolose) formalizace Berryho paradoxu k důkazu stejné věty je představen v kontextu prezentovaného přístupu. 1
Úplný záznam

Chcete být upozorněni, pokud se objeví nové záznamy odpovídající tomuto dotazu?
Přihlásit se k odběru RSS.
Digitální repozitář :: Hledej :: Nový záznam :: Personalizace :: Nápověda
Powered by Invenio v1.1.2
Spravuje admin.invenio@techlib.cz
Tato stránka je dostupná také v následujících jazycích:
Česky  English