Original title: Gödelovo dílo a jeho význam pro informatiku a filosofii
Translated title: Gödel's Work and its Significance for Computer Science and Philosophy
Authors: Bréda, Márton ; Havel, Martin (referee) ; Meduna, Alexandr (advisor)
Document type: Master’s theses
Year: 2026
Language: eng
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [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.
Keywords: 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; 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

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/260665

Permalink: http://www.nusl.cz/ntk/nusl-781439


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses