Computational Theory

Online only

978-80-574-0284-8

E - book for free download


Kľúčové slová:

Data sheet

Authors:Ľubomír Antoni - Stanislav Krajči
Year of publication:2024
Available from:15.02.2024
Edition:1st edition
Document type:Textbook
Publication language:Slovak
Faculty:Faculty of Science
Licencia:Creative Commons BY NC ND (Uveďte autora - Nepoužívajte komerčne - Nespracovávajte)

More info

An important part of theoretical computer science is the problem of Turing machines. This computational model has two basic properties: like any other computational program, the software of a Turing machine is composed of instructions, but in its case they are all of a single type. Every other (so far known) computer program can be transformed into a Turing machine program without loss of information. While the second feature reduces the question of what a calculator cannot do to the question of what a Turing machine cannot do, the first feature allows a much simpler investigation of such a question. Using this computational model, we can thus find concrete problems that no automaton can ever deal with (perhaps the most famous is the problem of the Turing machine stopping). Their existence demonstrates the fundamental limitations of (not only ideal) computational means, and thus encourages both criticality and humility in our thinking.

Related Products