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.