Recursive functions and metamathematics. Problems of completeness and decidability, Gödel's theorems
type: Item
instance of: scholarly article
title: Recursive functions and metamathematics. Problems of completeness and decidability, Gödel's theorems
zbMATH Open document ID: 0934.03001
author: Roman Murawski
published in: Synthese Library
publication date: 1999-12-06T00:00:00Z
review text: The mathematical developments stemming from Hilbert's program occupy a justifiably central place in mathematical logic in the 20th century. In particular, the brilliant work of Gödel on the completeness and incompleteness theorems in the 30's and the unfolding of the story by Turing, Post, and others, is surely one of the intellectual triumphs of mankind. Therefore, it is particularly apt that Murawski writes a text based on and around Gödel's theorems, concentrating on decidability and undecidability in the computational sense. Muraswki begins with around 50 pages devoted to the analysis of models of computation. He starts with the (total) recursive functions (formulated in a useful but slightly unusual way, as the class generated by successor, zero, dotted minus, substitution, and least number \(\mu(s)[f(x,s)=1]\) applied to only functions \(f(x,s)\) such that \(\forall x\exists s [f(x,s)=1]\)), then proceeds through Markov algorithms and Turing machines. Neither the equivalences are proved, although both are stated. This is also where the partial recursive functions are introduced. A number of examples are proven to be recursive, such as definition by cases and the like. Murawski then turns to an analysis of some of the computation hierarchies. In particular he looks at the arithmetical and Grzegorczyk hierarchies with an analysis of the primitive recursive functions. Various closure properties of these classes are proven, and related results discussed. The relevance of this material on the primitive recursive functions comes later when the author looks at the Paris-Harrington material and other work on mathematical incompletenesses of PA. Finally, the author discusses Church's Thesis. It is worth noting that the discussion of Church's Thesis is significantly more detailed than one would normally find in a mathematical text on computability, and even discusses opposition to the thesis. The second section of the book consists of a very detailed account of Gödel's …
Mathematics Subject Classification ID: 03-02
Mathematics Subject Classification ID: 03D20
Mathematics Subject Classification ID: 03-01
Mathematics Subject Classification ID: 03F30
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03-03
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 03D35
Mathematics Subject Classification ID: 03A05
zbMATH DE Number: 1374800
zbMATH Keywords: Gödel theorems
zbMATH Keywords: decidability
zbMATH Keywords: undecidability
zbMATH Keywords: models of computation
zbMATH Keywords: recursive functions
zbMATH Keywords: computation hierarchies
zbMATH Keywords: Church's thesis
zbMATH Keywords: incompleteness
zbMATH Keywords: complexity
zbMATH Keywords: philosophical consequences
zbMATH Keywords: Hilbert's program
reviewed by: Rodney G. Downey
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1374800