The Halting Problem and the Limits of Automation: Why No Tool Can Predict Every Program

Last Updated June 17, 2026

The halting problem is one of the clearest demonstrations that computation has limits. It asks a deceptively simple question: can there be a general algorithm that takes any program and any input, then determines whether that program will eventually stop or run forever? The answer is no.

This result is not a weakness of one programming language, one machine, one operating system, or one era of computing. It is a mathematical limit on algorithmic procedure itself. There is no universal automation tool that can decide the halting behavior of every possible program on every possible input.

The halting problem matters because many modern claims about automation depend on the idea that a sufficiently powerful system can inspect, predict, verify, or govern arbitrary computational behavior. Static analyzers, compilers, proof assistants, AI coding tools, model checkers, monitoring systems, and institutional automation can do many useful things. But they cannot erase the formal limits of procedure. The halting problem shows why some forms of complete automation are impossible in principle.

This article explains the halting problem as a foundation for understanding the limits of automation. It introduces program behavior, halting, nontermination, self-reference, diagonal reasoning, undecidability, recognizability, program analysis, Rice’s theorem, static analysis limits, verification limits, AI automation limits, bounded methods, practical safeguards, and responsible computational governance. The central lesson is not that automation is weak. The lesson is that automation must be scoped honestly.

Why the Halting Problem Matters

The halting problem matters because it separates useful automation from impossible automation. A tool can check many programs. It can detect many bugs. It can prove many properties. It can find many counterexamples. It can warn about many unsafe patterns. But no single general-purpose algorithm can decide the halting behavior of every possible program on every possible input.

This matters for software engineering, formal verification, compiler design, security analysis, AI coding assistants, institutional automation, and computational governance. Broad claims such as “this tool verifies all program behavior” or “this system can fully automate code review” must be treated carefully. Some properties can be checked under restrictions. Some can be approximated. Some can be checked for particular languages or bounded cases. But universal prediction of arbitrary program behavior is impossible.

The halting problem does not say that program analysis is useless. It says that program analysis cannot be universal without limits.

Back to top ↑

What the Halting Problem Asks

The halting problem asks whether there is a general algorithm that can decide, for any program \(P\) and input \(x\), whether \(P\) eventually halts when run on \(x\).

A hypothetical halting decider would take two things as input: a description of a program and the input to that program. It would return one of two answers: halts or does not halt. It would always return the correct answer and always stop.

The theorem says no such general algorithm exists.

The impossibility result applies to arbitrary programs. It does not prevent useful halting analysis for restricted cases.

Back to top ↑

Programs as Inputs

The halting problem depends on a powerful idea: programs can be represented as data. A program can be encoded as a string, number, file, syntax tree, bytecode sequence, or symbolic description. Once programs can be represented as data, other programs can analyze them.

This is the basis of compilers, interpreters, linters, static analyzers, verification tools, package managers, code search, AI coding assistants, and many forms of software automation. It is also what makes the halting problem possible to state.

The same representational power that makes automation possible also creates self-reference. A program can receive a representation of another program, or even a representation of itself.

Back to top ↑

Halting and Nontermination

A program halts when its execution stops. It may return a value, print output, reject an input, raise an error, or terminate with failure. Nontermination occurs when execution continues indefinitely.

Not all nontermination is accidental. Some systems are intended to run continuously: servers, operating systems, monitors, event loops, and streaming systems. In those cases, halting analysis may apply to individual requests, tasks, jobs, transactions, loops, or subroutines rather than to the entire system.

The halting problem concerns the general prediction of halt-or-not behavior for arbitrary programs and inputs. It does not say we can never know whether a particular program halts. Many particular cases can be proved, tested, bounded, or inspected successfully.

Back to top ↑

The Impossibility Result

The halting problem is undecidable. There is no algorithm that correctly decides, for every program \(P\) and input \(x\), whether \(P(x)\) halts.

This result is usually proved by contradiction. Suppose a perfect halting decider exists. Then we use that decider to construct another program that behaves in a deliberately contradictory way when given its own description. The contradiction shows that the original decider could not exist.

The result is not empirical. It is not based on current hardware limits. It is a theorem about the structure of computation.

Back to top ↑

Self-Reference and Diagonal Reasoning

Self-reference is central to the halting problem. Once programs can be represented as data, a program can be given its own description as input. This allows construction of programs that ask questions about themselves.

Diagonal reasoning is a method for showing that a proposed complete list or universal decision procedure cannot exist. In the halting proof, the diagonal construction builds a program that contradicts the predicted behavior assigned to itself.

Now ask what happens when \(D\) is run on its own description:

This contradiction means the assumed decider cannot exist. The proof uses self-reference not as a trick, but as a way to expose a limit in universal prediction.

Back to top ↑

Decidable vs. Recognizable

The halting problem is not decidable, but the set of halting program-input pairs is recognizable. This means there is a procedure that can confirm halting when halting actually occurs: run the program and wait. If it halts, the procedure can say yes. But if it does not halt, the waiting procedure may wait forever.

This distinction is essential. Recognition is not decision. A recognizer can eventually confirm yes cases. A decider must always halt with yes or no.

This distinction matters in practice. “No evidence yet” is not the same as “evidence of no.” A long-running process may be stuck, slow, waiting, or intentionally continuous. A tool must distinguish timeout, nontermination proof, unknown status, and ordinary delay.

Back to top ↑

Program Analysis and Static Checking

Program analysis tools inspect software to detect errors, infer properties, enforce rules, or prove limited claims. These tools are extremely useful. Compilers detect syntax and type errors. Linters flag suspicious patterns. Static analyzers find possible null dereferences, memory problems, unreachable code, race conditions, and security vulnerabilities. Model checkers explore state spaces under specified models.

The halting problem does not invalidate these tools. It explains why they must be limited. They may restrict the language, focus on specific properties, use approximations, require annotations, bound exploration, report unknown status, or allow false positives.

A mature analysis tool is honest about what it checks, what it approximates, and what it cannot know.

Back to top ↑

Rice’s Theorem and Program Properties

Rice’s theorem generalizes the lesson of the halting problem. It says, roughly, that every nontrivial semantic property of programs is undecidable for arbitrary programs. A semantic property is a property of what a program computes, not merely how the program is written.

For example, asking whether an arbitrary program ever returns a particular value, whether it computes a constant function, whether it accepts all inputs, or whether it is equivalent to another arbitrary program can fall into undecidable territory.

This does not prevent practical checking. It means practical checking must be scoped: restricted languages, restricted properties, bounded inputs, proof annotations, abstract interpretation, runtime monitoring, or human review.

Back to top ↑

Limits of Automation

The halting problem places a boundary around universal automation. A system cannot fully automate all reasoning about arbitrary programs. It cannot guarantee complete prediction of every possible computational behavior. It cannot replace every form of specification, proof, review, monitoring, and judgment.

Automation can still be powerful when it is bounded. It can reject invalid programs, detect many errors, prove many specific properties, generate tests, search for counterexamples, check proofs, enforce schemas, and monitor runtime behavior. The danger comes when bounded automation is marketed or used as if it were unlimited.

The responsible response is not to reject automation. It is to design automation with explicit boundaries.

Back to top ↑

Bounded Automation and Practical Tools

Most useful tools work by accepting limits. They restrict what they analyze, ask for annotations, use type systems, bound search depth, approximate program behavior, report uncertainty, or focus on specific classes of errors. These limits are not defects. They are how automation becomes practical and honest.

A good tool should be able to say “yes,” “no,” “unknown,” “out of scope,” or “requires review” when appropriate.

Back to top ↑

AI and the Halting Boundary

AI systems can assist computational reasoning. They can explain code, suggest tests, identify likely bugs, generate documentation, propose invariants, translate between languages, summarize traces, and help users think through possible failures. But AI systems do not eliminate the halting problem.

A language model may give a plausible answer about whether a program halts. That answer may be useful as a hypothesis, explanation, or review aid. But plausibility is not a universal decision procedure. A probabilistic or generative system cannot turn an undecidable problem into a decidable one for all arbitrary programs.

The right framing is “AI in the toolkit, never in control.” AI can support reasoning, but it should not be mistaken for a universal solver of formal limits.

Back to top ↑

Back to top ↑

Mathematics, Computation, and Modeling

The halting problem can be stated as a decision problem over encoded programs and inputs. Let \(\langle P,x\rangle\) represent an encoded pair consisting of program \(P\) and input \(x\).

A decider for \(HALT\) would be a machine \(H\) such that:

The theorem says:

But \(HALT\) is recognizable:

This distinction supports a practical governance lesson:

Back to top ↑

Python Workflow: Halting Boundary Audit

The Python workflow below creates a synthetic audit for automation claims affected by the halting boundary. It scores program-scope clarity, termination-claim clarity, undecidability awareness, bounded-analysis honesty, unknown-status handling, timeout policy, false-certainty risk, human-review pathway, traceability, and governance readiness.

# halting_boundary_audit.py
# Dependency-light workflow for evaluating automation claims near the halting boundary.

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 HaltingBoundaryCase:
    case_name: str
    automation_context: str
    automation_claim: str
    program_scope_clarity: float
    termination_claim_clarity: float
    undecidability_awareness: float
    bounded_analysis_honesty: float
    unknown_status_handling: float
    timeout_policy: float
    false_certainty_risk_control: float
    human_review_pathway: 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 halting_boundary_quality(case: HaltingBoundaryCase) -> float:
    return clamp(
        100.0 * (
            0.10 * case.program_scope_clarity
            + 0.12 * case.termination_claim_clarity
            + 0.12 * case.undecidability_awareness
            + 0.10 * case.bounded_analysis_honesty
            + 0.10 * case.unknown_status_handling
            + 0.08 * case.timeout_policy
            + 0.12 * case.false_certainty_risk_control
            + 0.10 * case.human_review_pathway
            + 0.08 * case.traceability
            + 0.08 * case.governance_readiness
        )
    )


def automation_overclaim_risk(case: HaltingBoundaryCase) -> float:
    weak_points = [
        1.0 - case.termination_claim_clarity,
        1.0 - case.undecidability_awareness,
        1.0 - case.bounded_analysis_honesty,
        1.0 - case.unknown_status_handling,
        1.0 - case.false_certainty_risk_control,
        1.0 - case.human_review_pathway,
        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 halting-boundary posture with clear automation limits"
    if quality >= 68 and risk <= 38:
        return "usable halting-boundary posture with review needs"
    if risk >= 55:
        return "high automation-overclaim risk; halting and unknown-status limits may be unclear"
    return "partial halting-boundary posture; strengthen boundedness, unknown handling, review, or governance"


def build_cases() -> list[HaltingBoundaryCase]:
    return [
        HaltingBoundaryCase(
            case_name="Static analyzer",
            automation_context="Tool checks source code for selected error classes.",
            automation_claim="Analyzer detects scoped patterns and reports unknown status when analysis is incomplete.",
            program_scope_clarity=0.86,
            termination_claim_clarity=0.78,
            undecidability_awareness=0.80,
            bounded_analysis_honesty=0.84,
            unknown_status_handling=0.82,
            timeout_policy=0.76,
            false_certainty_risk_control=0.80,
            human_review_pathway=0.74,
            traceability=0.80,
            governance_readiness=0.76,
        ),
        HaltingBoundaryCase(
            case_name="AI code review assistant",
            automation_context="Generative model explains code and suggests possible issues.",
            automation_claim="Assistant supports review but does not decide arbitrary termination or correctness.",
            program_scope_clarity=0.66,
            termination_claim_clarity=0.62,
            undecidability_awareness=0.58,
            bounded_analysis_honesty=0.68,
            unknown_status_handling=0.60,
            timeout_policy=0.64,
            false_certainty_risk_control=0.62,
            human_review_pathway=0.78,
            traceability=0.60,
            governance_readiness=0.72,
        ),
        HaltingBoundaryCase(
            case_name="Formal verification workflow",
            automation_context="Verifier checks specified properties under formal assumptions.",
            automation_claim="Workflow proves bounded or specified properties, not universal behavior of all programs.",
            program_scope_clarity=0.82,
            termination_claim_clarity=0.80,
            undecidability_awareness=0.84,
            bounded_analysis_honesty=0.82,
            unknown_status_handling=0.78,
            timeout_policy=0.72,
            false_certainty_risk_control=0.80,
            human_review_pathway=0.80,
            traceability=0.84,
            governance_readiness=0.82,
        ),
        HaltingBoundaryCase(
            case_name="Institutional automation workflow",
            automation_context="Rule engine routes cases through automated checks and human review.",
            automation_claim="Clear cases are automated while ambiguous or unresolved cases are escalated.",
            program_scope_clarity=0.80,
            termination_claim_clarity=0.76,
            undecidability_awareness=0.64,
            bounded_analysis_honesty=0.78,
            unknown_status_handling=0.84,
            timeout_policy=0.82,
            false_certainty_risk_control=0.78,
            human_review_pathway=0.88,
            traceability=0.86,
            governance_readiness=0.88,
        ),
    ]


def run_audit() -> list[dict[str, object]]:
    rows: list[dict[str, object]] = []
    for case in build_cases():
        quality = halting_boundary_quality(case)
        risk = automation_overclaim_risk(case)
        rows.append({
            **asdict(case),
            "halting_boundary_quality": round(quality, 3),
            "automation_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_halting_boundary_quality": round(mean(float(row["halting_boundary_quality"]) for row in rows), 3),
        "average_automation_overclaim_risk": round(mean(float(row["automation_overclaim_risk"]) for row in rows), 3),
        "highest_quality_case": max(rows, key=lambda row: float(row["halting_boundary_quality"]))["case_name"],
        "highest_risk_case": max(rows, key=lambda row: float(row["automation_overclaim_risk"]))["case_name"],
        "interpretation": "Halting-boundary quality depends on scope clarity, termination claims, undecidability awareness, bounded-analysis honesty, unknown-status handling, timeout policy, false-certainty control, human review, traceability, and governance."
    }


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

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

    print("Halting boundary audit complete.")
    print(TABLES / "halting_boundary_audit.csv")


if __name__ == "__main__":
    main()

This workflow treats the halting problem as a practical governance boundary. It asks whether automation claims distinguish known, unknown, bounded, approximate, out-of-scope, and review-required cases.

Back to top ↑

R Workflow: Automation-Limit Summary

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

# halting_boundary_summary.R
# Base R workflow for summarizing halting-boundary and automation-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, "halting_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_halting_boundary_quality = mean(data$halting_boundary_quality),
  average_automation_overclaim_risk = mean(data$automation_overclaim_risk),
  highest_quality_case = data$case_name[which.max(data$halting_boundary_quality)],
  highest_risk_case = data$case_name[which.max(data$automation_overclaim_risk)]
)

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

comparison_matrix <- rbind(
  data$halting_boundary_quality,
  data$automation_overclaim_risk
)

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

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

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

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

grid()
dev.off()

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

dimension_means <- colMeans(data[, c(
  "program_scope_clarity",
  "termination_claim_clarity",
  "undecidability_awareness",
  "bounded_analysis_honesty",
  "unknown_status_handling",
  "timeout_policy",
  "false_certainty_risk_control",
  "human_review_pathway",
  "traceability",
  "governance_readiness"
)]) * 100

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

grid()
dev.off()

print(summary_table)

This workflow helps compare static analyzers, AI code review tools, formal verification workflows, institutional automation systems, and other automated reasoning tools by how honestly they handle unknowns and limits.

Back to top ↑

GitHub Repository

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

articles/the-halting-problem-and-the-limits-of-automation/
├── python/
│   ├── halting_boundary_audit.py
│   ├── self_reference_examples.py
│   ├── diagonal_reasoning_examples.py
│   ├── recognizability_examples.py
│   ├── automation_limit_examples.py
│   ├── calculators/
│   │   ├── halting_boundary_calculator.py
│   │   └── automation_overclaim_risk_calculator.py
│   └── tests/
├── r/
│   ├── halting_boundary_summary.R
│   ├── automation_limit_visualization.R
│   └── unknown_status_report.R
├── julia/
│   ├── halting_boundary_simulation.jl
│   └── recognizability_model_examples.jl
├── sql/
│   ├── schema_halting_cases.sql
│   ├── schema_automation_limits.sql
│   └── halting_boundary_queries.sql
├── haskell/
│   ├── HaltingBoundaryTypes.hs
│   ├── AutomationLimits.hs
│   └── Main.hs
├── rust/
│   └── src/
├── go/
│   └── main.go
├── c/
│   └── halting_boundary_audit.c
├── cpp/
│   └── halting_boundary_audit.cpp
├── fortran/
│   └── halting_boundary_model.f90
├── java/
│   └── src/main/java/org/contentcatalyst/algorithms/
├── typescript/
│   └── src/
├── prolog/
│   └── halting_boundary_rules.pl
├── racket/
│   └── halting_interpreter.rkt
├── docs/
│   ├── methodology.md
│   ├── article-notes.md
│   ├── the-halting-problem-and-the-limits-of-automation.md
│   ├── governance-notes.md
│   └── responsible-use.md
├── data/
│   └── synthetic_halting_boundary_cases.csv
├── outputs/
│   ├── tables/
│   ├── figures/
│   ├── json/
│   ├── logs/
│   └── reports/
├── notebooks/
│   └── the_halting_problem_and_the_limits_of_automation_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 Halting-Aware Automation

A practical method for halting-aware automation begins by rejecting universal claims unless they are formally justified within a restricted domain. The goal is not to make automation timid. The goal is to make it honest.

A halting-aware system does not pretend to know everything. It provides useful automation while preserving uncertainty where uncertainty is structurally unavoidable.

Back to top ↑

Common Pitfalls

A common pitfall is assuming that because a tool works on many examples, it can decide all cases. This is false. Passing many tests, checking many programs, or producing many plausible explanations does not overcome the halting problem.

Another pitfall is hiding unknown status. A system that reports only “pass” or “fail” may create false certainty if it has no way to represent out-of-scope, timeout, incomplete analysis, or undecidable uncertainty.

Common pitfalls include:

• universal automation claims: implying that a tool can decide arbitrary program behavior;
• confusing timeout with nontermination: treating “did not finish within a limit” as proof that a program never halts;
• confusing simulation with decision: running a program can confirm halting, but cannot generally confirm nonhalting;
• ignoring unknown status: forcing all cases into pass/fail categories;
• overtrusting AI explanations: treating plausible reasoning as a formal decision procedure;
• hiding false positives and false negatives: presenting analysis results without limitations;
• forgetting scope restrictions: omitting language, model, property, or boundedness assumptions;
• losing counterexamples: failing to preserve traces that reveal failures;
• governance gaps: leaving unresolved high-stakes cases without escalation;
• false certainty: treating bounded or approximate automation as complete proof.

The remedy is clear procedural language: proved, checked, bounded, sampled, inferred, suggested, unknown, out of scope, or requires review.

Back to top ↑

Why the Halting Problem Still Matters

The halting problem still matters because automation keeps expanding. Software tools analyze code. AI systems generate and inspect programs. Institutions automate workflows. Scientific systems rely on simulations. Public systems use rules, models, and decision pipelines. In each setting, people may be tempted to treat automated output as final.

The halting problem teaches a different lesson. Computation is powerful, but procedure has limits. Some questions cannot be answered by a universal algorithm. Some tools must be bounded. Some cases must remain unknown. Some decisions require human review, formal assumptions, domain judgment, and governance.

This is not an argument against automation. It is an argument for responsible automation. Useful systems should state what they can decide, what they can only approximate, what they cannot know, and how unresolved cases are handled. The halting problem gives computational reasoning one of its most important forms of humility.

Back to top ↑

Related Articles

• What Is Algorithms & Computational Reasoning?
• Logic and Computation
• Formal Languages and Symbolic Representation
• Proof, Correctness, and Algorithmic Verification
• Termination, Invariants, and Edge Cases
• Computability and the Limits of Procedure
• Automated Reasoning and Mechanical Inference
• Lambda Calculus, Functions, and Formal Computation
• Formal Methods and Machine-Checked Reasoning

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.
• 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.
• 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.
• Rice, H.G. (1953) ‘Classes of recursively enumerable sets and their decision problems’, Transactions of the American Mathematical Society, 74(2), pp. 358–366. Available through: American Mathematical Society.
• 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.
• 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.
• 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.
• Rice, H.G. (1953) ‘Classes of recursively enumerable sets and their decision problems’, Transactions of the American Mathematical Society, 74(2), pp. 358–366. Available at: https://www.ams.org/journals/tran/1953-074-02/.
• 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 ↑