# Category Archives: logic.2013

## Turing Machines

An algorithm must be seen to be believed. –Donald Knuth In the age defined by computing, we are apt to forget that the quest to solve mathematical problems algorithmically, by a mechanical procedure terminating in finitely many steps, dates back … Continue reading

## Tennenbaum’s Theorem

Gödel’s Incompleteness Theorems established two fundamental types of incompleteness phenomena in first-order arithmetic (and stronger theories). The First Incompleteness Theorem showed that no recursive axiomatization extending ${\rm PA}$ can decide all properties of natural numbers and the Second Incompleteness Theorem … Continue reading

## The Second Incompleteness Theorem

There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable. There is another theory … Continue reading

## The First Incompleteness Theorem

Some people are always critical of vague statements. I tend rather to be critical of precise statements; they are the only ones which can correctly be labeled ‘wrong’. –Raymond Smullyan At the dawn of the $20^{\text{th}}$-century formal mathematics flourished. In … Continue reading

## Recursive Functions

To understand recursion, you must understand recursion. In his First Incompleteness Theorem paper, Gödel provided the first explicit definition of the class of primitive recursive functions on the natural numbers ($\mathbb N^k\to\mathbb N$). Properties of functions on the natural numbers … Continue reading