Talks and Poster Presentations (with Proceedings-Entry):
"On the Halting Problem of Finite-State Programs";
Talk: 14. Kolloquium "Programmiersprachen und Grundlagen der Programmierung (KPS'07)",
Timmendorfer Strand, Germany;
- 2007-10-12; in: "14. Kolloquium Programmiersprachen und Grundlagen der Programmierung",
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
Created from the Publication Database of the Vienna University of Technology.