[Back]


Talks and Poster Presentations (with Proceedings-Entry):

R. Kirner:
"On the Halting Problem of Finite-State Programs";
Talk: 14. Kolloquium "Programmiersprachen und Grundlagen der Programmierung (KPS'07)", Timmendorfer Strand, Germany; 2007-10-10 - 2007-10-12; in: "14. Kolloquium Programmiersprachen und Grundlagen der Programmierung", (2007), 6 pages.



English abstract:
The undecidability of the halting problem is a well-known
research result of theoretical computer science, dating back to Turing´s
work in 1936. Nevertheless, it is commonly known that the halting problem
on finite-state computer systems is decidable. Thus, any undecidability
proof given for the halting problem must imply that it does not
apply to finite-state computer systems.
The aim of this paper is to deepen the understanding of why the undecidability
proofs of the halting problem cannot be instantiated as finite-state
programs. To bridge the gap between theory and practice, the arguments
are based on simple mathematics rather than an extensive use of abstract
formalisms.