Název: Gödelovo dílo a jeho význam pro informatiku a filosofii
Překlad názvu: Gödel's Work and its Significance for Computer Science and Philosophy
Autoři: Bréda, Márton ; Havel, Martin (oponent) ; Meduna, Alexandr (vedoucí práce)
Typ dokumentu: Diplomové práce
Rok: 2026
Jazyk: eng
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [eng] [cze]
Tato práce zkoumá dopad práce Kurta Gödela, zejména jeho vět o neúplnosti, na informatiku. První část se zabývá Gödelovými filozofickými současníky – včetně Russella, Carnapa, Wittgensteina a Tarského – a jejich vlivem na něj samotného, porovnává jeho výsledky s výsledky Alana Turinga a diskutuje jejich filozofické důsledky pro mechanismus, umělou inteligenci a problém P versus NP. Hlavní přínos práce je technický: popisuje existující logický systém (statická výpočetní logika, SCL a omezená varianta) rozšiřující logiku prvního řádu o sebereferenci a dokazuje, že formule v této logice lze transformovat do univerzální logiky druhého řádu. Pomocí Faginovy věty je tato transformace spojena s vyčíslitelností a je implementována aplikace, která kompiluje SCL formule přímo do tabulky přechodů ko-nedeterministického Turingova stroje. This thesis explores the impact of Kurt Gödel's work, especially his Incompleteness Theorems, on computer science. Its first part surveys Gödel's philosophical contemporaries — including Russell, Carnap, Wittgenstein, and Tarski — and their influence on him, compares his results with Alan Turing's, and discusses their philosophical consequences for Mechanism, artificial intelligence, and the P versus NP problem. The thesis's main contribution is technical: it describes an~exsisting logical system (static computation logic, SCL, and a bounded variant) extending first-order logic with self-reference, and proves that formulas in this logic can be transformed into universal second-order logic. Using Fagin's Theorem, this transformation is connected to computability, and an application is implemented that compiles SCL formulas directly into the transition table of a co-nondeterministic Turing Machine.
Klíčová slova: Computability theory; Descriptive complexity; Fagin's Theorem; Formal logic compilation; Game-theoretic semantics; Gödel's Incompleteness Theorems; Nondeterministic Turing Machine construction; Philosophy of mathematics; Second-order logic; Turing Machines; deskriptivní složitost; Faginova věta; filozofie matematiky; Gödelovy věty o neúplnosti; herní sémantika; kompilace formální logiky; konstrukce nedeterministického Turingova stroje; logika druhého řádu; teorie vyčíslitelnosti; Turingovy stroje

Instituce: Vysoké učení technické v Brně (web)
Informace o dostupnosti dokumentu: Plný text je dostupný v Digitální knihovně VUT.
Původní záznam: http://hdl.handle.net/11012/260665

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-781439


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Diplomové práce