DeepRead
Cover of Theory of recursive functions and effective computability

Theory of recursive functions and effective computability

Hartley Rogers · 1957

Programming and computer science › Lisp and Scheme

#10,799 most recommended

About the book

A graduate-level mathematics textbook on the theory of computable (recursive) functions and the sets and relations associated with them. It covers the formal models of effective computation, including Turing machines and general recursive functions, along with enumerability, decidability, and the arithmetical hierarchy. The book's central claim is that the informal notion of effective computability can be captured by precise mathematical definitions, and that several independently proposed formalisms define the same class of functions. This equivalence is presented as support for the Church-Turing thesis. The text then uses these tools to establish limits on what can be computed or decided, including results in the style of Gödel's incompleteness theorems.

Written by Claude from what it knows of this book.

What Hacker News says 33% recommend · 0% critical

02.5520092015202020262009 peak · 1
This bookAverage book in Lisp and Scheme

In the commenters’ own words

  • For me, personally, I really like the lambda calculus as a tool to organize and better my computational thinking. I came into programming/computer science…

    cybernautique · 2021 · in Turing Oversold?

  • Rogers "Theory of Recursive Functions and Effective Computability", page 1, emphasis is the author's: § 1.1 The informal notion of algorithm In this chapter…

    qsort · 2026 · in Claude Is Not a Compiler

What Open Library readers say

No Open Library reader has rated it yet.

  • 1 want to read
  • 0 reading
  • 0 have read

Open Library’s page for the book

What critics say, via Wikipedia

No Wikipedia article about this book yet, so no critics to quote.

Reddit communities — coming later

The threads it came up in

Details

First published
1957
ISBN
9780262680523
Editions known
4 at Open Library
Open Library
OL9153527W

Computable functionsRecursive functionsSymbolic and mathematical Logic

Explore in the mosaic

Read next: its neighbours on the mosaic