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.

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.

Created from the Publication Database of the Vienna University of Technology.