On the Halting Problem

This paper discusses the Halting Problem, its meaning, context, and proofs.

Introduction

In 1900, German mathematician David Hilbert published 23 mathematical problems, systematically referred to today as Hilbert’s problems. This paper will focus on the effects of one of those problems, and its relevance in computer theory and modern computing systems. The halting problem asks simple question: is it possible to know, with complete certainty, whether or not a computation is possible before attempting the computation itself? Allan Turing was notably one of the first to conclude that this is an impossible feat to accomplish.

Read the Paper

Download