Knowledge base: Warsaw University of Technology

Settings and your account

Back

Hilbert-Ackermann decision problem and its solution by Church and Turing

Michalina Marta Wysocka

Abstract

The thesis is focused on the question posed by David Hilbert and Wilhelm Ackermann in 1928, whether there might exist a universal procedure that determines the truthness or falsity of any mathematical hypothesis. Their question is called Entscheidungsproblem, and is considered a fundamental problem of mathematical logic - if there existed such a procedure, it would be possible to solve any mathematical problem in a purely mechanical manner. In order to give an answer to the Entscheidungsproblem, it was necessary to find the procedure or prove that it cannot exist. In the thirties of the twentieth century several methods have been developed thanks to which it was possible to do that by proving that the procedure does not exist; two of them, proposed independently by Alan Turing and Alonzo Church, will be described in the thesis. The first one uses the notion of a Turing machine, which is a mathematical model for defining an algorithm, and on which the functioning of computers is based. The second one, proposed by Alonzo Church, makes use of the definition of recursive functions, which according to Church’s Thesis, are the same functions as those whose values can be computed in a mechanical way. Also, examples of undecidable problems will be given, for which there cannot exist a proce- dure for determining mechanically whether the answer to the question posed in the problem is positive or negative. The conclusion that one might come to from the fact of the existence of undecidable problems, is that computers, despite artificial intelligence being developed, will never be able to replace the nonmechanical thinking entirely.
Diploma type
Engineer's / Bachelor of Science
Diploma type
Bachelor thesis
Author
Michalina Marta Wysocka (FMIS) Michalina Marta Wysocka,, Faculty of Mathematics and Information Science (FMIS)
Title in Polish
Problem decyzyjny Hilberta-Ackermanna i jego rozwiązanie przez Churcha i Turinga
Supervisor
Jan Spaliński (FMIS/DIE) Jan Spaliński,, Department of Integral Equations (FMIS/DIE)Faculty of Mathematics and Information Science (FMIS)
Certifying unit
Faculty of Mathematics and Information Science (FMIS)
Affiliation unit
Department of Integral Equations (FMIS/DIE)
Study subject / specialization
, Matematyka
Language
(pl) Polish
Status
Finished
Defense Date
06-11-2019
Issue date (year)
2019
Reviewers
Jan Spaliński (FMIS/DIE) Jan Spaliński,, Department of Integral Equations (FMIS/DIE)Faculty of Mathematics and Information Science (FMIS) Jerzy Wyborski (FMIS/DODE) Jerzy Wyborski,, Department of Ordinary Differential Equations (FMIS/DODE)Faculty of Mathematics and Information Science (FMIS)
Keywords in Polish
problem decyzji, Entscheidungsproblem, David Hilbert, Wilhelm Ackermann, Alan Turing, maszyna Turinga, Alonzo Church, funkcje rekurencyjne, funkcje pierwotnie reku- rencyjne, funckcja Ackermanna, równania diofantyczne
Keywords in English
decision problem, Entscheidungsproblem, David Hilbert, Wilhelm Ackermann, Alan Turing, Turing machine, Alonzo Church, recursive functions, primitive recursive functions, Ack- ermann function, diophantine equations
Abstract in Polish
Praca skupia się na postawionym w 1928 roku przez Davida Hilberta i Wilhelma Ackermanna pytaniu, czy istnieje uniwersalna procedura ustalająca prawdziwość lub fałszywość dowolnej hipo- tezy matematycznej. Problem przez nich postawiony, nazywany Entscheidungsproblem, uważany jest za fundamentalny problem logiki matematycznej - gdyby istniała taka procedura, możliwe byłoby rozwiązanie każdego problemu matematycznego w sposób czysto mechaniczny. Aby roz- strzygnąć Entscheidungsproblem, należałoby znaleźć tę procedurę bądź udowodnić, że taka nie istnieje. W latach 30. dwudziestego wieku zaproponowano kilka metod, dzięki którym była moż- liwa odpowiedź na pytanie Hilberta i Ackermanna, i wykazanie, że nie ma takiej procedury; dwie z nich, opracowane niezależnie przez Alana Turinga i Alonzo Churcha, zostaną opisane w tej pracy. Pierwsza korzysta z pojęcia maszyny Turinga, będącej matematycznym modelem służącym do wykonywania algorytmów, na którym opiera się działanie komputerów. Na przykładzie gry lo- gicznej stworzonej przez węgierskiego matematyka, opisane zostanie działanie maszyny Turinga. Druga metoda, zaproponowana przez Alonzo Churcha, korzysta z definicji funkcji rekurencyj- nych stanowiących, zgodnie z Tezą Churcha, te same funkcje, których wartości można obliczyć w sposób mechaniczny. Podane zostaną również przykłady nierozstrzygalnych problemów, czyli takich, dla których nie może istnieć procedura, dzięki której dałoby się mechanicznie odpowiedzieć twierdząco lub przecząco na postawione w nich pytania. Wnioskiem, jaki można wyciągnąć z faktu istnienia problemów nierozstrzygalnych jest to, że działanie komputerów, mimo rozwijającej się sztucznej inteligencji, nigdy nie będzie w stanie całkowicie zastąpić myślenia niemechanicznego.
File
  • File: 1
    praca_dyplomowa.pdf
Request a WCAG compliant version
Local fields
Identyfikator pracy APD: 9208

Uniform Resource Identifier
https://repo.pw.edu.pl/info/bachelor/WUT68b4238cce334d9a8be72794dd97a74a/
URN
urn:pw-repo:WUT68b4238cce334d9a8be72794dd97a74a

Confirmation
Are you sure?
Report incorrect data on this page