---
title: "Computability and Unsolvability"
authors:
  - "Martin Davis"
year: 1958
venue: "McGraw-Hill; Dover reprint 1985"
arxiv: null
doi: null
source: "https://store.doverpublications.com/products/9780486614717"
topics:
  - computability
  - davis
  - hilbert-tenth
seed_rank: 635
seed_batch: "foundations-greats-2026-08-13"
reviewed: "2026-08-13"
pool: "maths-foundations"
relevance_score: 8
lineage: foundations-of-computing
cites:
  - title: "On Computable Numbers, with an Application to the Entscheidungsproblem"
    url: "https://doi.org/10.1112/plms/s2-42.1.230"
    year: 1936
    arxiv: null
    doi: "10.1112/plms/s2-42.1.230"
  - title: "An Unsolvable Problem of Elementary Number Theory"
    url: "https://doi.org/10.2307/2371045"
    year: 1936
    arxiv: null
    doi: "10.2307/2371045"
  - title: "Introduction to Metamathematics"
    url: "https://www.worldcat.org/title/introduction-to-metamathematics/oclc/523589"
    year: 1952
    arxiv: null
    doi: null
see:
  - "515-on-computable-numbers-with-an-application-to-the-entscheidun"
  - "507-an-unsolvable-problem-of-elementary-number-theory"
  - "529-introduction-to-metamathematics"
---

# Computability and Unsolvability

## One-sentence takeaway

Davis’s 1958 textbook standardizes recursive-function / Turing-machine computability for a generation and already frames Hilbert’s tenth problem as the next unsolvability target.

## Why it matters here

Textbook carrier for the foundations spine. Davis also edited *The Undecidable* (636); together they are how Gödel–Church–Turing–Post reached people who were not reading 1930s German journals.

## Key ideas

- Partial recursive functions, r.e. sets, and many-one / Turing reducibility presented as a single toolkit.
- Classic unsolvability examples (halting, word problems) worked in uniform style.
- Early systematic treatment of Diophantine sets — the path to the DPRM theorem / Hilbert’s tenth.
- McGraw-Hill 1958; Dover 1985 reprint (ISBN 978-0-486-61471-7) is the in-print edition.

## Caveats

## Links

- Dover edition: https://store.doverpublications.com/products/9780486614717