Computability and the Limits of Procedure: What Algorithms Can and Cannot Solve

Last Updated June 17, 2026

Computation is powerful because procedures can be written down, followed, repeated, automated, analyzed, and implemented in machines. But not every question can be answered by a procedure. Not every problem has an algorithm. Not every true statement can be mechanically derived. Not every program behavior can be predicted by a general tool.

Computability studies the boundary between what can and cannot be solved by algorithmic procedure. It asks a foundational question: which problems are computable in principle, regardless of speed, hardware, programming language, or implementation skill? This question is deeper than efficiency. A problem may be slow but computable. Another may be impossible for any general procedure.

Computability and the limits of procedure matter because modern systems often assume that enough data, automation, modeling, or artificial intelligence can eventually resolve any formalized question. Computability theory shows why that assumption is false. Some limits are not temporary engineering obstacles. They are mathematical limits on procedure itself.

This article introduces computability as a foundation of computational reasoning. It explains effective procedures, algorithms, decision problems, decidability, recognizability, Turing machines, the Church-Turing thesis, computable functions, undecidable problems, semidecidability, reduction, the halting problem, limits of automation, and the difference between computability and efficiency. It also connects computability to software, verification, artificial intelligence, modeling, institutions, and responsible automation.

Why Computability Matters

Computability matters because algorithms are often treated as if they can solve any sufficiently formal problem. In practice, computational systems are powerful, but they are not unlimited. Some problems cannot be solved by a general algorithm at all. This is true even before we ask whether the algorithm would be fast enough.

This distinction is essential. A slow problem may become practical through better algorithms, improved hardware, parallelism, approximation, or heuristics. An uncomputable problem cannot be solved by a universal procedure merely by scaling resources. It requires reformulation, restriction, approximation, human judgment, or acceptance that no general solution exists.

Computability gives computational reasoning humility. It shows that formalization does not automatically create solvability.

Back to top ↑

What Computability Means

A problem is computable if there exists an algorithmic procedure that solves it for every input in its defined domain. The procedure must be finite, explicit, mechanically followable, and guaranteed to return the required result.

Computability is not about whether people currently know the best algorithm. It is about whether any algorithm exists in principle. The central question is not “Can this be done quickly?” but “Can this be done by procedure at all?”

Computability therefore sits underneath algorithm design. Before asking how efficient a procedure is, we first ask whether a procedure can exist.

Back to top ↑

Procedure, Algorithm, and Effective Method

Computability theory formalizes the idea of an effective method: a step-by-step procedure that can be carried out mechanically. Such a method does not depend on intuition, creativity, or hidden judgment during execution. It must specify what to do at every step.

This does not mean that designing the algorithm is mechanical. Human creativity may be required to discover a procedure. But once the procedure exists, its execution must be definite enough that a machine could follow it.

Computability asks whether such a procedure exists. If it does not, the problem is not merely hard. It lies beyond general algorithmic solution.

Back to top ↑

Decision Problems and Decidability

Many computability questions are expressed as decision problems: problems with yes-or-no answers. This format is useful because it isolates whether a procedure can always return a correct answer.

For example: Is a number prime? Does a string belong to a language? Does a graph contain a path between two nodes? Does a program halt on a given input? Some decision problems are decidable. Others are undecidable.

A decidable problem has a procedure that halts with yes or no on every valid input. A recognizable problem may have a procedure that confirms yes cases but runs forever on some no cases. This distinction is central to computability.

Back to top ↑

Turing Machines and Computation

A Turing machine is a mathematical model of computation. It is not meant to be a practical computer design. It is a simple formal model that captures the idea of mechanical procedure.

A Turing machine has a tape, a head that reads and writes symbols, a finite set of states, and rules for moving from one state to another. Despite its simplicity, it can model any computation that is generally understood to be algorithmic.

Turing machines make it possible to reason precisely about computation. They allow computability theory to prove that some problems are solvable by algorithm and others are not.

Back to top ↑

The Church-Turing Thesis

The Church-Turing thesis states, informally, that any effectively calculable function can be computed by a Turing machine. It is not a theorem in the ordinary sense because “effectively calculable” is an informal concept. But it is one of the central ideas in the foundations of computation.

Different formal models of computation were developed in the early twentieth century, including Turing machines, lambda calculus, and recursive functions. These models turned out to characterize the same class of computable functions. That convergence gives strong support to the thesis.

The thesis helps explain why computability results are so general. If a problem is impossible for a Turing machine in the formal sense, it is not merely impossible for one programming language or one hardware design. It is impossible for algorithmic procedure as such, under the standard model of effective computation.

Back to top ↑

Decidable, Recognizable, and Undecidable

A decidable language has a machine that halts and correctly accepts or rejects every input. A recognizable language has a machine that accepts every yes input, but it may fail to halt on no inputs. An undecidable language has no decider.

This distinction matters because some problems allow confirmation but not guaranteed rejection. For example, a search process may eventually find a proof if one exists, but if no proof exists, the search may never know when to stop.

The difference between “no answer yet” and “no” is crucial. In undecidable settings, waiting longer may help in some cases, but no general procedure can guarantee resolution for all cases.

Back to top ↑

Reduction and Impossibility Proofs

Reduction is a method for showing relationships between problems. If solving problem \(B\) would allow us to solve problem \(A\), then a procedure for \(B\) is at least as powerful as needed for \(A\). If \(A\) is already known to be undecidable, this can show that \(B\) is undecidable too.

Reductions are important because impossibility results often spread. Once one problem is known to be undecidable, many other problems can be shown undecidable by reducing the known impossible problem to them.

Reductions are central to theoretical computer science because they convert isolated impossibility results into maps of computational limits.

Back to top ↑

The Halting Problem as a Boundary

The halting problem asks whether there is a general algorithm that can determine, for any program and input, whether that program will eventually halt. The answer is no. There is no general procedure that decides halting for all possible program-input pairs.

This result is one of the most important boundaries in computation. It shows that program behavior cannot be fully predicted by a universal mechanical checker. Many other limits in verification, static analysis, program equivalence, and automated reasoning are connected to this boundary.

The next article in this series focuses directly on the halting problem and the limits of automation. Here, the key point is that computability theory gives a general framework for understanding why such limits exist.

Back to top ↑

Computability vs. Complexity

Computability and complexity are related but distinct. Computability asks whether a problem can be solved by an algorithm at all. Complexity asks how much time, memory, communication, or other resources are required by algorithms that solve it.

A computable problem may still be practically impossible at large scale. An undecidable problem is different: no general algorithm exists to solve all cases, no matter how much time or memory is provided.

This distinction prevents confusion. A problem can be computable but infeasible. A different problem can be undecidable and therefore not solvable by any universal algorithmic procedure.

Back to top ↑

Limits of Automation

Computability theory places limits on automation. If no general procedure can solve a problem, then no software tool, AI system, static analyzer, theorem prover, or institutional workflow can solve it universally without changing the problem.

This does not make automation useless. It means automation must be scoped. Tools can solve restricted versions of problems. They can approximate. They can search for evidence. They can find counterexamples. They can verify specific properties. They can handle bounded cases. They can support human reasoning. But they cannot eliminate all undecidable boundaries.

The limit is not a failure of modern tools. It is a structural feature of computation.

Back to top ↑

Computability in Real Systems

Real systems rarely present themselves as textbook computability problems. They appear as software tools, validators, data pipelines, simulations, rule engines, AI systems, model-checking workflows, compiler checks, governance processes, and institutional decision systems.

Computability still matters because real systems often make broad claims about automation. A tool may claim to detect every bug, classify every case, verify every policy, or infer every relevant pattern. Computability theory reminds us to ask: what exactly is being decided, for which input domain, under which restrictions, and with what guarantee?

A mature computational system is honest about what it can decide, what it can only approximate, and what must remain open to review.

Back to top ↑

Back to top ↑

Mathematics, Computation, and Modeling

Computability can be expressed through functions and languages. Let \(f\) be a function over inputs \(x\).

A function is computable when there exists an algorithm \(A\) that returns \(f(x)\) for every valid input \(x\).

For a decision problem, the output is yes or no:

A language \(L\) is decidable if there is a machine that halts on every input and correctly accepts or rejects:

A recognizable language requires only that yes cases eventually be accepted:

These definitions turn informal questions about procedure into precise mathematical claims.

Back to top ↑

Python Workflow: Computability Boundary Audit

The Python workflow below creates a synthetic audit for computability boundaries in computational systems. It scores procedure definition, input-domain clarity, decision-status clarity, termination guarantee, recognizability status, reduction awareness, approximation honesty, automation-scope clarity, traceability, and governance readiness.

# computability_boundary_audit.py
# Dependency-light workflow for evaluating computability and procedure-limit claims.

from __future__ import annotations

from dataclasses import asdict, dataclass
from pathlib import Path
import csv
import json
from statistics import mean

ARTICLE_ROOT = Path(__file__).resolve().parents[1]
TABLES = ARTICLE_ROOT / "outputs" / "tables"
JSON_DIR = ARTICLE_ROOT / "outputs" / "json"


@dataclass(frozen=True)
class ComputabilityBoundaryCase:
    case_name: str
    computational_context: str
    procedural_claim: str
    procedure_definition: float
    input_domain_clarity: float
    decision_status_clarity: float
    termination_guarantee: float
    recognizability_status: float
    reduction_awareness: float
    approximation_honesty: float
    automation_scope_clarity: float
    traceability: float
    governance_readiness: float


def clamp(value: float, low: float = 0.0, high: float = 100.0) -> float:
    return max(low, min(high, value))


def computability_boundary_quality(case: ComputabilityBoundaryCase) -> float:
    return clamp(
        100.0 * (
            0.10 * case.procedure_definition
            + 0.10 * case.input_domain_clarity
            + 0.12 * case.decision_status_clarity
            + 0.12 * case.termination_guarantee
            + 0.10 * case.recognizability_status
            + 0.10 * case.reduction_awareness
            + 0.10 * case.approximation_honesty
            + 0.10 * case.automation_scope_clarity
            + 0.08 * case.traceability
            + 0.08 * case.governance_readiness
        )
    )


def procedural_overclaim_risk(case: ComputabilityBoundaryCase) -> float:
    weak_points = [
        1.0 - case.decision_status_clarity,
        1.0 - case.termination_guarantee,
        1.0 - case.recognizability_status,
        1.0 - case.reduction_awareness,
        1.0 - case.approximation_honesty,
        1.0 - case.automation_scope_clarity,
        1.0 - case.traceability,
        1.0 - case.governance_readiness,
    ]
    return clamp(100.0 * mean(weak_points))


def diagnose(quality: float, risk: float) -> str:
    if quality >= 82 and risk <= 22:
        return "strong computability-boundary posture with clear procedure limits"
    if quality >= 68 and risk <= 38:
        return "usable computability-boundary posture with review needs"
    if risk >= 55:
        return "high procedural overclaim risk; automation limits may be unclear"
    return "partial computability-boundary posture; clarify decidability, termination, approximation, or governance"


def build_cases() -> list[ComputabilityBoundaryCase]:
    return [
        ComputabilityBoundaryCase(
            case_name="Static analyzer",
            computational_context="Tool checks code for selected classes of errors.",
            procedural_claim="The analyzer detects specified patterns but does not decide all program behavior.",
            procedure_definition=0.84,
            input_domain_clarity=0.82,
            decision_status_clarity=0.78,
            termination_guarantee=0.82,
            recognizability_status=0.72,
            reduction_awareness=0.66,
            approximation_honesty=0.80,
            automation_scope_clarity=0.84,
            traceability=0.78,
            governance_readiness=0.74,
        ),
        ComputabilityBoundaryCase(
            case_name="General program verifier",
            computational_context="Verification tool attempts to prove properties of arbitrary programs.",
            procedural_claim="Verification is sound for specified properties and restricted models, not universal for all behavior.",
            procedure_definition=0.78,
            input_domain_clarity=0.74,
            decision_status_clarity=0.70,
            termination_guarantee=0.62,
            recognizability_status=0.68,
            reduction_awareness=0.78,
            approximation_honesty=0.74,
            automation_scope_clarity=0.72,
            traceability=0.76,
            governance_readiness=0.76,
        ),
        ComputabilityBoundaryCase(
            case_name="AI reasoning assistant",
            computational_context="Generative system supports reasoning, code review, explanation, and search.",
            procedural_claim="The system assists reasoning but does not provide a universal decision procedure.",
            procedure_definition=0.66,
            input_domain_clarity=0.62,
            decision_status_clarity=0.58,
            termination_guarantee=0.64,
            recognizability_status=0.56,
            reduction_awareness=0.50,
            approximation_honesty=0.68,
            automation_scope_clarity=0.62,
            traceability=0.58,
            governance_readiness=0.72,
        ),
        ComputabilityBoundaryCase(
            case_name="Institutional rule engine",
            computational_context="Rule system assigns cases to categories under documented policies.",
            procedural_claim="Rules decide in-scope cases and route ambiguous or out-of-domain cases for review.",
            procedure_definition=0.82,
            input_domain_clarity=0.78,
            decision_status_clarity=0.76,
            termination_guarantee=0.80,
            recognizability_status=0.70,
            reduction_awareness=0.54,
            approximation_honesty=0.76,
            automation_scope_clarity=0.82,
            traceability=0.84,
            governance_readiness=0.86,
        ),
    ]


def run_audit() -> list[dict[str, object]]:
    rows: list[dict[str, object]] = []
    for case in build_cases():
        quality = computability_boundary_quality(case)
        risk = procedural_overclaim_risk(case)
        rows.append({
            **asdict(case),
            "computability_boundary_quality": round(quality, 3),
            "procedural_overclaim_risk": round(risk, 3),
            "diagnostic": diagnose(quality, risk),
        })
    return rows


def write_csv(path: Path, rows: list[dict[str, object]]) -> None:
    path.parent.mkdir(parents=True, exist_ok=True)
    with path.open("w", newline="", encoding="utf-8") as handle:
        writer = csv.DictWriter(handle, fieldnames=list(rows[0].keys()))
        writer.writeheader()
        writer.writerows(rows)


def write_json(path: Path, payload: object) -> None:
    path.parent.mkdir(parents=True, exist_ok=True)
    path.write_text(json.dumps(payload, indent=2, sort_keys=True), encoding="utf-8")


def summarize(rows: list[dict[str, object]]) -> dict[str, object]:
    return {
        "case_count": len(rows),
        "average_computability_boundary_quality": round(mean(float(row["computability_boundary_quality"]) for row in rows), 3),
        "average_procedural_overclaim_risk": round(mean(float(row["procedural_overclaim_risk"]) for row in rows), 3),
        "highest_quality_case": max(rows, key=lambda row: float(row["computability_boundary_quality"]))["case_name"],
        "highest_risk_case": max(rows, key=lambda row: float(row["procedural_overclaim_risk"]))["case_name"],
        "interpretation": "Computability-boundary quality depends on procedure definition, input-domain clarity, decision status, termination guarantees, recognizability, reduction awareness, approximation honesty, automation scope, traceability, and governance."
    }


def main() -> None:
    rows = run_audit()
    summary = summarize(rows)

    write_csv(TABLES / "computability_boundary_audit.csv", rows)
    write_csv(TABLES / "computability_boundary_audit_summary.csv", [summary])
    write_json(JSON_DIR / "computability_boundary_audit.json", rows)
    write_json(JSON_DIR / "computability_boundary_audit_summary.json", summary)

    print("Computability boundary audit complete.")
    print(TABLES / "computability_boundary_audit.csv")


if __name__ == "__main__":
    main()

This workflow treats computability as a governance and reasoning boundary. It asks whether a system states what it can decide, what it can only recognize, what it approximates, what it cannot guarantee, and how automation claims are bounded.

Back to top ↑

R Workflow: Procedure-Limit Summary

The R workflow reads the Python-generated audit table and creates summary outputs and visualizations using base R. It compares computability-boundary quality and procedural-overclaim risk across synthetic computational systems.

# computability_boundary_summary.R
# Base R workflow for summarizing computability and procedural-limit claims.

args <- commandArgs(trailingOnly = FALSE)
file_arg <- grep("^--file=", args, value = TRUE)

if (length(file_arg) > 0) {
  script_path <- normalizePath(sub("^--file=", "", file_arg[1]), mustWork = TRUE)
  article_root <- normalizePath(file.path(dirname(script_path), ".."), mustWork = TRUE)
} else {
  article_root <- getwd()
}

setwd(article_root)

tables_dir <- file.path(article_root, "outputs", "tables")
figures_dir <- file.path(article_root, "outputs", "figures")

if (!dir.exists(tables_dir)) {
  dir.create(tables_dir, recursive = TRUE)
}

if (!dir.exists(figures_dir)) {
  dir.create(figures_dir, recursive = TRUE)
}

input_path <- file.path(tables_dir, "computability_boundary_audit.csv")

if (!file.exists(input_path)) {
  stop(paste("Missing", input_path, "Run the Python workflow first."))
}

data <- read.csv(input_path, stringsAsFactors = FALSE)

summary_table <- data.frame(
  case_count = nrow(data),
  average_computability_boundary_quality = mean(data$computability_boundary_quality),
  average_procedural_overclaim_risk = mean(data$procedural_overclaim_risk),
  highest_quality_case = data$case_name[which.max(data$computability_boundary_quality)],
  highest_risk_case = data$case_name[which.max(data$procedural_overclaim_risk)]
)

write.csv(
  summary_table,
  file.path(tables_dir, "r_computability_boundary_summary.csv"),
  row.names = FALSE
)

comparison_matrix <- rbind(
  data$computability_boundary_quality,
  data$procedural_overclaim_risk
)

colnames(comparison_matrix) <- data$case_name
rownames(comparison_matrix) <- c("Computability-boundary quality", "Procedural-overclaim risk")

png(
  file.path(figures_dir, "computability_boundary_quality_vs_risk.png"),
  width = 1400,
  height = 800
)

barplot(
  comparison_matrix,
  beside = TRUE,
  las = 2,
  ylim = c(0, 100),
  ylab = "Score",
  main = "Computability Boundary Quality vs. Procedural Overclaim Risk"
)

legend(
  "topleft",
  legend = rownames(comparison_matrix),
  pch = 15,
  bty = "n"
)

grid()
dev.off()

png(
  file.path(figures_dir, "computability_boundary_dimensions.png"),
  width = 1400,
  height = 800
)

dimension_means <- colMeans(data[, c(
  "procedure_definition",
  "input_domain_clarity",
  "decision_status_clarity",
  "termination_guarantee",
  "recognizability_status",
  "reduction_awareness",
  "approximation_honesty",
  "automation_scope_clarity",
  "traceability",
  "governance_readiness"
)]) * 100

barplot(
  dimension_means,
  las = 2,
  ylim = c(0, 100),
  ylab = "Average score",
  main = "Average Computability-Boundary Evidence by Dimension"
)

grid()
dev.off()

print(summary_table)

This workflow helps compare automation claims across static analyzers, program verifiers, AI tools, institutional rule engines, and other procedural systems.

Back to top ↑

GitHub Repository

The companion repository for this article will provide reproducible code, synthetic datasets, workflow documentation, generated outputs, and computability-boundary diagnostics that extend the article into executable examples.

articles/computability-and-the-limits-of-procedure/
├── python/
│   ├── computability_boundary_audit.py
│   ├── decidability_examples.py
│   ├── recognizability_examples.py
│   ├── reduction_examples.py
│   ├── halting_boundary_examples.py
│   ├── calculators/
│   │   ├── computability_boundary_calculator.py
│   │   └── procedural_overclaim_risk_calculator.py
│   └── tests/
├── r/
│   ├── computability_boundary_summary.R
│   ├── procedure_limit_visualization.R
│   └── automation_scope_report.R
├── julia/
│   ├── computability_boundary_simulation.jl
│   └── decision_problem_examples.jl
├── sql/
│   ├── schema_computability_cases.sql
│   ├── schema_procedure_limits.sql
│   └── computability_queries.sql
├── haskell/
│   ├── DecidabilityTypes.hs
│   ├── ProcedureLimits.hs
│   └── Main.hs
├── rust/
│   └── src/
├── go/
│   └── main.go
├── c/
│   └── computability_boundary_audit.c
├── cpp/
│   └── computability_boundary_audit.cpp
├── fortran/
│   └── computability_boundary_model.f90
├── java/
│   └── src/main/java/org/contentcatalyst/algorithms/
├── typescript/
│   └── src/
├── prolog/
│   └── decidability_rules.pl
├── racket/
│   └── computability_interpreter.rkt
├── docs/
│   ├── methodology.md
│   ├── article-notes.md
│   ├── computability-and-the-limits-of-procedure.md
│   ├── governance-notes.md
│   └── responsible-use.md
├── data/
│   └── synthetic_computability_boundary_cases.csv
├── outputs/
│   ├── tables/
│   ├── figures/
│   ├── json/
│   ├── logs/
│   └── reports/
├── notebooks/
│   └── computability_and_the_limits_of_procedure_walkthrough.ipynb
├── canvas/
│   ├── canvas_manifest.json
│   ├── canvas_cards.json
│   └── canvas_index.md
└── shared/
    ├── schemas/
    ├── templates/
    ├── taxonomies/
    ├── benchmarks/
    └── governance/

Back to top ↑

A Practical Method for Computability Thinking

A practical method for computability thinking begins by separating problem definition from automation ambition. Before claiming that a system can solve, decide, verify, or automate something, ask what kind of procedural claim is being made.

This method is useful for algorithm design, software tools, AI products, verification systems, rule engines, institutional workflows, scientific modeling, and public decision support.

Back to top ↑

Common Pitfalls

A common pitfall is confusing practical failure with theoretical impossibility. A slow algorithm is not the same as an undecidable problem. Conversely, an undecidable problem will not become decidable simply through more compute, more data, or a larger model.

Another pitfall is treating automation as universal because it works on many examples. A system may perform well on a class of cases while still lacking a general decision procedure. This is especially important for program analysis, AI reasoning, institutional decision systems, and automated verification.

Common pitfalls include:

• confusing computability with complexity: treating expensive problems and undecidable problems as the same;
• overclaiming automation: presenting a bounded tool as if it were a universal decision procedure;
• ignoring input domain: failing to state which cases the procedure actually covers;
• mistaking recognition for decision: treating “eventually finds yes cases” as “always decides yes or no”;
• hiding nontermination: failing to distinguish no result yet from a negative result;
• forgetting reductions: missing connections to known undecidable problems;
• formalism without limits: assuming that formal expression guarantees procedural solvability;
• AI overconfidence: assuming generative fluency dissolves computability boundaries;
• governance gaps: leaving unresolved, ambiguous, or undecidable cases without review paths;
• false certainty: presenting approximations, heuristics, or bounded checks as complete guarantees.

The remedy is disciplined language: say what is decidable, what is recognizable, what is bounded, what is approximate, what is unknown, and what requires human review.

Back to top ↑

Why the Limits of Procedure Matter

Computability and the limits of procedure show that algorithms have boundaries. Some problems can be solved by effective methods. Some can be recognized but not decided. Some can be approximated, bounded, sampled, or restricted. Some cannot be solved by any general algorithmic procedure.

This does not weaken computational reasoning. It strengthens it. Knowing the limits of procedure helps people design better algorithms, make more honest automation claims, build safer verification tools, interpret AI systems more carefully, and create governance processes for cases that should not be reduced to mechanical decision.

The lesson is not that computation is weak. The lesson is that computation is precise. It can do extraordinary things when the problem, representation, procedure, and assumptions are well defined. But its power is not infinite. Responsible algorithmic reasoning includes knowing where procedure ends.

Back to top ↑

Related Articles

• What Is Algorithms & Computational Reasoning?
• Problems, Procedures, and Formalization
• Logic and Computation
• Formal Languages and Symbolic Representation
• Proof, Correctness, and Algorithmic Verification
• Termination, Invariants, and Edge Cases
• The Halting Problem and the Limits of Automation
• Automated Reasoning and Mechanical Inference
• Lambda Calculus, Functions, and Formal Computation

Further Reading

• Church, A. (1936) ‘An unsolvable problem of elementary number theory’, American Journal of Mathematics, 58(2), pp. 345–363. Available through: JSTOR.
• Cooper, S.B. (2004) Computability Theory. Boca Raton, FL: Chapman & Hall/CRC. Publisher information available at: Routledge.
• Cutland, N.J. (1980) Computability: An Introduction to Recursive Function Theory. Cambridge: Cambridge University Press. Available at: Cambridge University Press.
• Davis, M. (1958) Computability and Unsolvability. New York: McGraw-Hill. Dover reprint information available at: Dover Publications.
• Davis, M. (ed.) (1965) The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Hewlett, NY: Raven Press. Dover edition information available at: Dover Publications.
• Enderton, H.B. (2011) Computability Theory: An Introduction to Recursion Theory. Amsterdam: Elsevier. Publisher information available at: Elsevier.
• Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2006) Introduction to Automata Theory, Languages, and Computation. 3rd edn. Boston, MA: Pearson. Publisher information available at: Pearson.
• Rogers, H. (1987) Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press. Available at: MIT Press.
• Sipser, M. (2012) Introduction to the Theory of Computation. 3rd edn. Boston, MA: Cengage Learning. Publisher information available at: Cengage.
• Soare, R.I. (2016) Turing Computability: Theory and Applications. Berlin: Springer. Available at: SpringerLink.
• Turing, A.M. (1936) ‘On computable numbers, with an application to the Entscheidungsproblem’, Proceedings of the London Mathematical Society, s2-42(1), pp. 230–265. Available at: Oxford Academic.

References

• Church, A. (1936) ‘An unsolvable problem of elementary number theory’, American Journal of Mathematics, 58(2), pp. 345–363. Available at: https://www.jstor.org/stable/2371045.
• Cooper, S.B. (2004) Computability Theory. Boca Raton, FL: Chapman & Hall/CRC. Publisher information available at: https://www.routledge.com/Computability-Theory/Cooper/p/book/9781584882374.
• Cutland, N.J. (1980) Computability: An Introduction to Recursive Function Theory. Cambridge: Cambridge University Press. Available at: https://www.cambridge.org/core/books/computability/28F57B73FB658E4F19D2BF9B14B9795D.
• Davis, M. (1958) Computability and Unsolvability. New York: McGraw-Hill. Dover edition available at: https://store.doverpublications.com/products/9780486614717.
• Davis, M. (ed.) (1965) The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Hewlett, NY: Raven Press. Dover edition available at: https://store.doverpublications.com/products/9780486432281.
• Enderton, H.B. (2011) Computability Theory: An Introduction to Recursion Theory. Amsterdam: Elsevier. Available at: https://shop.elsevier.com/books/computability-theory/enderton/978-0-12-384958-8.
• Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2006) Introduction to Automata Theory, Languages, and Computation. 3rd edn. Boston, MA: Pearson. Publisher information available at: https://www.pearson.com/en-us/subject-catalog/p/introduction-to-automata-theory-languages-and-computation/P200000003439.
• Rogers, H. (1987) Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press. Available at: https://mitpress.mit.edu/9780262680523/theory-of-recursive-functions-and-effective-computability/.
• Sipser, M. (2012) Introduction to the Theory of Computation. 3rd edn. Boston, MA: Cengage Learning. Publisher information available at: https://www.cengage.com/c/introduction-to-the-theory-of-computation-3e-sipser/.
• Soare, R.I. (2016) Turing Computability: Theory and Applications. Berlin: Springer. Available at: https://link.springer.com/book/10.1007/978-3-642-31933-4.
• Turing, A.M. (1936) ‘On computable numbers, with an application to the Entscheidungsproblem’, Proceedings of the London Mathematical Society, s2-42(1), pp. 230–265. doi: 10.1112/plms/s2-42.1.230.

Back to top ↑