Alonzo Church, Lambda Calculus, and Formal Computation: Functions, Computability, and Logic

Last Updated June 23, 2026

Alonzo Church, Lambda Calculus, and Formal Computation examines one of the most important routes by which computation became mathematically precise. If Alan Turing gave computation a machine model, Church gave computation a functional and symbolic model: a formal language in which functions, application, abstraction, substitution, and reduction could be studied as objects of logic.

Church’s lambda calculus is astonishingly spare. It does not begin with hardware, tapes, registers, or memory cells. It begins with expressions, variables, functions, and application. A function can be formed by abstraction. A function can be applied to an argument. An expression can be reduced by substitution. From these minimal ideas, a whole theory of computation emerges.

Church’s importance is not only technical. His work helped define effective calculability, contributed to the proof that the Entscheidungsproblem has no general solution, influenced the Church-Turing thesis, shaped recursion theory and mathematical logic, and later became foundational for functional programming languages, type theory, proof assistants, programming-language semantics, and formal reasoning. Church shows that computation is not only machine motion. It is also symbolic transformation under rules.

This article introduces Alonzo Church, lambda calculus, formal computation, functions, abstraction, application, variables, substitution, beta reduction, alpha conversion, eta conversion, normal form, recursion, fixed points, Church numerals, lambda definability, effective calculability, recursive functions, the Entscheidungsproblem, Church’s theorem, Church-Turing thesis, type theory, functional programming, programming-language semantics, proof assistants, formal reasoning, and responsible computational interpretation. It argues that Church matters because he showed how computation can be modeled without machines: as a formal calculus of functions and transformations.

Why Church Matters

Church matters because he gave computation a formal language of functions. Turing’s machine model shows computation as stepwise action by an abstract device. Church’s lambda calculus shows computation as expression transformation. Both routes became central to modern computability. Together they helped clarify what effective computation means.

Church’s work also matters because it connects logic, functions, proof, programming languages, and formal systems. Lambda calculus is not merely a historical curiosity. It remains a foundation for functional programming, programming-language theory, denotational semantics, type theory, proof assistants, and formal reasoning about programs.

Church matters because he made computation legible as formal function transformation.

Back to top ↑

Formal Computation Without Machines

Lambda calculus is a model of computation without a machine. It has no tape, no head, no register, and no hardware. It uses expressions. A computation occurs when one expression is transformed into another according to formal rules. This makes lambda calculus especially important for understanding computation abstractly.

Machine-free computation is not non-computational. It is another way of capturing effective procedure. In lambda calculus, the essential action is application and reduction. The expression itself contains the structure of the computation.

Church shows that computation can be modeled as formal transformation even when no machine picture is used.

Back to top ↑

What Is Lambda Calculus?

Lambda calculus is a formal notation for functions, application, and abstraction. Its syntax is intentionally minimal. A variable can stand for an input. A lambda abstraction forms a function. An application applies one expression to another. Computation occurs through reduction, especially beta reduction: applying a function to an argument by substituting the argument for the bound variable.

The power of lambda calculus is that this small system can express rich computation. Numbers, booleans, pairs, conditionals, recursion, and data structures can be encoded using functions.

Lambda calculus is minimal, but its minimalism is exactly what makes it foundational.

Back to top ↑

Functions, Application, and Abstraction

The three central ideas of lambda calculus are functions, application, and abstraction. A function is represented by abstraction: λx. M means a function with input x and body M. Application is written by placing expressions together: M N means apply M to N. These simple forms make functions into first-class objects.

This matters because functions are not merely tools applied from outside. They can be passed, returned, composed, and applied to other functions. This is a major root of functional programming and higher-order computation.

Church’s calculus makes functions into the basic medium of computation.

Back to top ↑

Variables, Binding, and Scope

Lambda calculus depends on careful treatment of variables. A variable can be bound by a lambda abstraction or free within an expression. Scope determines where a binding applies. Without careful handling of binding and scope, substitution can accidentally capture variables and change meaning.

This issue remains central in programming-language design. Variables, closures, lexical scope, substitution, name binding, and capture avoidance all have roots in formal systems like lambda calculus.

Formal computation requires not only symbols, but rules for how symbols bind and transform.

Back to top ↑

Substitution and Beta Reduction

Beta reduction is the core computational step of lambda calculus. It says that applying an abstraction to an argument reduces by substituting the argument for the bound variable in the body of the function. In symbolic form: (λx. M) N reduces to M[x := N].

This is computation as replacement under discipline. The replacement must respect binding and avoid variable capture. The result is not an arbitrary rewriting, but a rule-governed transformation.

Beta reduction makes computation visible as a sequence of formal transformations.

Back to top ↑

Alpha Conversion and the Problem of Names

Alpha conversion is the rule that bound variable names can be changed without changing the meaning of an expression. For example, λx. x and λy. y are structurally the same identity function. The name is not the meaning; the binding structure is the meaning.

This idea has deep implications. It shows that formal systems must distinguish symbols that carry structural roles from the particular names used to write them. In programming, this appears in variable renaming, lexical scope, compiler transformations, and equivalence of functions.

Alpha conversion shows that names matter less than binding structure.

Back to top ↑

Eta Conversion and Extensionality

Eta conversion expresses a form of functional equivalence. If a function f and the function λx. f x behave the same for all x, then they may be treated as equivalent under suitable conditions. This connects lambda calculus with the idea that functions can be understood by what they do when applied.

Eta conversion matters because it links syntax and behavior. Two expressions may look different but have the same functional behavior. This issue remains central in program equivalence, optimization, compiler design, and formal semantics.

Eta conversion shows how formal computation moves between expression structure and functional behavior.

Back to top ↑

Normal Forms and Evaluation

A lambda expression is in normal form when no further beta reductions can be performed. Not every expression has a normal form. Some expressions reduce forever. This gives lambda calculus its own version of termination and nontermination.

Evaluation strategy matters. Normal-order reduction and applicative-order reduction can behave differently. Some strategies may find a normal form when one exists; others may diverge. This anticipates major programming-language questions: eager vs lazy evaluation, termination, control flow, and operational semantics.

Evaluation strategy turns formal reduction into a theory of program behavior.

Back to top ↑

Church Numerals and Encoding

One of the striking achievements of lambda calculus is that numbers can be encoded as functions. Church numerals represent natural numbers by repeated application of a function. Zero applies a function zero times. One applies it once. Two applies it twice. In this way, arithmetic can be represented without primitive numbers.

This is important because it shows how data can be encoded inside a formal system. Booleans, pairs, lists, and control structures can also be encoded. Computation becomes a matter of representation and reduction.

Church numerals show that computation depends on encoding as much as on calculation.

Back to top ↑

Recursion, Fixed Points, and Self-Reference

Lambda calculus has no named functions in its pure form, yet it can express recursion through fixed-point combinators. A fixed point of a function F is a value x such that F x = x. Fixed-point combinators allow functions to refer to their own behavior indirectly.

This is one of the places where formal computation becomes philosophically powerful. Recursion, self-reference, and nontermination are not programming accidents. They are structural possibilities in sufficiently expressive formal systems.

Fixed points reveal the expressive depth of formal computation—and the roots of nontermination.

Back to top ↑

Effective Calculability and Church’s Thesis

Church’s work on effective calculability proposed that the intuitive notion of effectively calculable functions could be identified with formally definable classes, including lambda-definability and recursiveness. This was a major step toward the Church-Turing thesis.

The thesis is not a theorem in the ordinary sense because it connects an intuitive informal notion—effective computation—with formal models. Its strength comes from convergence: lambda calculus, recursive functions, and Turing machines define the same class of computable functions under standard formulations.

Church’s thesis connects formal systems to the intuitive idea of mechanical method.

Back to top ↑

The Entscheidungsproblem and Undecidability

Church’s work helped answer the Entscheidungsproblem negatively. There is no general effective procedure that decides every valid formula of first-order logic. This result helped mark a boundary for formal reasoning: not every mathematical question can be settled by a universal decision method.

This is as important as the positive theory of computation. Lambda calculus is powerful, but formal systems also reveal limits. The dream of complete mechanical decision has boundaries, and those boundaries are part of computational reasoning.

Church’s undecidability result is a foundational warning against unlimited automation.

Back to top ↑

Church and Turing

Church and Turing approached computation differently but arrived at convergent foundations. Church used lambda calculus and recursive functions. Turing used a machine model based on finite symbolic action. The fact that these approaches coincide in computational power is one reason the concept of computability became so robust.

Turing’s model became especially intuitive for computer architecture and machine execution. Church’s model became especially influential for functions, programming-language semantics, type theory, and formal systems. Both are necessary for a rich history of computation.

Church and Turing together show that computation is not tied to one image: it can be functional, mechanical, symbolic, and formal.

Back to top ↑

Type Theory and Formal Systems

Church’s work also matters for type theory. Type systems classify expressions and constrain how functions can be applied. This is crucial for avoiding contradictions, structuring formal reasoning, and designing programming languages that catch errors before execution.

Church’s simple type theory and later typed lambda calculi connect logic and computation. Types can be understood as specifications, propositions, interfaces, or constraints. In modern systems, types help programmers and proof assistants reason about correctness.

Church’s influence extends from computability into the formal architecture of programming and proof.

Back to top ↑

Functional Programming and Modern Computation

Lambda calculus became a foundation for functional programming. Languages such as Lisp, Scheme, ML, Haskell, OCaml, F#, and many modern programming-language features draw from lambda-calculus ideas. Anonymous functions, closures, higher-order functions, recursion, immutability, lazy evaluation, type inference, and functional composition all have roots in this tradition.

This does not mean every functional language is pure lambda calculus. Real languages add types, data structures, effects, modules, input/output, compilers, runtimes, and libraries. But lambda calculus provides a conceptual core: computation as expression evaluation.

Modern programming still carries Church’s insight: computation can be organized as functions applied to structured expressions.

Back to top ↑

Formal Reasoning and AI Caution

Church’s legacy also matters for AI-era caution. Lambda calculus and formal computation show the power of precise systems. But they also show that formalization requires definitions, syntax, semantics, rules, and scope. A system does not become reliable merely because it produces outputs. Its reasoning must be represented, evaluated, and constrained.

Modern AI systems often operate statistically rather than by transparent lambda-calculus reduction. Still, Church’s formal tradition helps clarify what it means to specify a system, define an operation, evaluate an expression, check a type, or prove a property. It reminds us that apparent reasoning and formal reasoning are not the same thing.

Church’s legacy supports disciplined formal reasoning, not blind faith in automated output. AI belongs in the toolkit, not in control.

Back to top ↑

Back to top ↑

Mathematics, Computation, and Modeling

A lambda term can be modeled as:

Beta reduction can be modeled as:

Alpha conversion can be modeled as:

Church numerals can be modeled as:

The Church-Turing convergence can be modeled as:

These formulas are simplified teaching models. They clarify Church’s contribution without replacing formal study of lambda calculus or computability theory.

Back to top ↑

Python Workflow: Lambda Calculus Computation Map

The Python workflow below creates a dependency-light interpretive map of Church’s contribution to lambda calculus and formal computation. It scores themes by formalization, functional abstraction, symbolic transformation, substitution, reduction, computability, undecidability, type influence, programming relevance, and AI caution, then writes reproducible CSV and JSON outputs.

# alonzo_church_lambda_calculus_map.py
# Dependency-light workflow for mapping Church's role in lambda calculus and formal computation.

from __future__ import annotations

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

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


@dataclass(frozen=True)
class ChurchConfig:
    article: str = "alonzo_church_lambda_calculus_and_formal_computation"
    core_threshold: float = 0.80
    high_formalization_threshold: float = 0.86


def timestamp_utc() -> str:
    return datetime.now(timezone.utc).isoformat()


def write_csv(path: Path, rows: list[dict[str, object]]) -> None:
    path.parent.mkdir(parents=True, exist_ok=True)
    if not rows:
        path.write_text("", encoding="utf-8")
        return
    fieldnames = sorted({key for row in rows for key in row.keys()})
    with path.open("w", newline="", encoding="utf-8") as handle:
        writer = csv.DictWriter(handle, fieldnames=fieldnames, extrasaction="ignore")
        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 church_themes() -> list[dict[str, object]]:
    return [
        {"theme_id": "lambda_calculus_core", "formalization": 0.98, "functional_abstraction": 0.98, "symbolic_transformation": 0.98, "substitution": 0.96, "reduction": 0.96, "computability": 0.96, "undecidability": 0.86, "type_influence": 0.88, "programming_relevance": 0.98, "ai_caution": 0.86},
        {"theme_id": "effective_calculability", "formalization": 0.98, "functional_abstraction": 0.94, "symbolic_transformation": 0.94, "substitution": 0.90, "reduction": 0.92, "computability": 0.98, "undecidability": 0.92, "type_influence": 0.82, "programming_relevance": 0.92, "ai_caution": 0.90},
        {"theme_id": "entscheidungsproblem_undecidability", "formalization": 0.98, "functional_abstraction": 0.88, "symbolic_transformation": 0.92, "substitution": 0.86, "reduction": 0.88, "computability": 0.98, "undecidability": 0.98, "type_influence": 0.78, "programming_relevance": 0.88, "ai_caution": 0.96},
        {"theme_id": "church_turing_convergence", "formalization": 0.98, "functional_abstraction": 0.94, "symbolic_transformation": 0.94, "substitution": 0.86, "reduction": 0.90, "computability": 0.98, "undecidability": 0.94, "type_influence": 0.82, "programming_relevance": 0.94, "ai_caution": 0.92},
        {"theme_id": "church_numerals_encoding", "formalization": 0.92, "functional_abstraction": 0.98, "symbolic_transformation": 0.96, "substitution": 0.94, "reduction": 0.94, "computability": 0.94, "undecidability": 0.76, "type_influence": 0.84, "programming_relevance": 0.96, "ai_caution": 0.82},
        {"theme_id": "recursion_fixed_points", "formalization": 0.94, "functional_abstraction": 0.98, "symbolic_transformation": 0.98, "substitution": 0.96, "reduction": 0.98, "computability": 0.96, "undecidability": 0.88, "type_influence": 0.86, "programming_relevance": 0.98, "ai_caution": 0.86},
        {"theme_id": "type_theory_and_proofs", "formalization": 0.96, "functional_abstraction": 0.92, "symbolic_transformation": 0.90, "substitution": 0.88, "reduction": 0.88, "computability": 0.88, "undecidability": 0.78, "type_influence": 0.98, "programming_relevance": 0.94, "ai_caution": 0.92},
        {"theme_id": "functional_programming_legacy", "formalization": 0.88, "functional_abstraction": 0.98, "symbolic_transformation": 0.92, "substitution": 0.86, "reduction": 0.92, "computability": 0.90, "undecidability": 0.74, "type_influence": 0.92, "programming_relevance": 0.98, "ai_caution": 0.84},
    ]


def score_theme(row: dict[str, object], config: ChurchConfig) -> dict[str, object]:
    formal_score = mean([
        float(row["formalization"]),
        float(row["functional_abstraction"]),
        float(row["symbolic_transformation"]),
        float(row["substitution"]),
        float(row["reduction"]),
        float(row["computability"]),
        float(row["undecidability"]),
        float(row["type_influence"]),
        float(row["programming_relevance"]),
        float(row["ai_caution"]),
    ])

    if formal_score >= config.core_threshold and float(row["formalization"]) >= config.high_formalization_threshold:
        interpretive_status = "core_church_formal_computation_thread"
    elif formal_score >= config.core_threshold:
        interpretive_status = "major_church_formal_computation_thread"
    else:
        interpretive_status = "supporting_church_formal_computation_thread"

    return {
        "theme_id": row["theme_id"],
        "formalization": round(float(row["formalization"]), 6),
        "functional_abstraction": round(float(row["functional_abstraction"]), 6),
        "symbolic_transformation": round(float(row["symbolic_transformation"]), 6),
        "substitution": round(float(row["substitution"]), 6),
        "reduction": round(float(row["reduction"]), 6),
        "computability": round(float(row["computability"]), 6),
        "undecidability": round(float(row["undecidability"]), 6),
        "type_influence": round(float(row["type_influence"]), 6),
        "programming_relevance": round(float(row["programming_relevance"]), 6),
        "ai_caution": round(float(row["ai_caution"]), 6),
        "formal_score": round(formal_score, 6),
        "interpretive_status": interpretive_status,
    }


def interpretation_cautions() -> list[dict[str, str]]:
    return [
        {"caution": "do_not_treat_lambda_calculus_as_ordinary_algebra", "meaning": "Lambda calculus is a formal system of functions, application, abstraction, and reduction."},
        {"caution": "do_not_confuse_lambda_calculus_with_machine_hardware", "meaning": "Church models computation through expressions, not physical machines."},
        {"caution": "do_not_ignore_binding_and_scope", "meaning": "Substitution requires careful handling of free and bound variables."},
        {"caution": "do_not_treat_church_turing_thesis_as_simple_theorem", "meaning": "The thesis connects informal effective calculability with formal models."},
        {"caution": "do_not_forget_undecidability", "meaning": "Church's legacy includes formal limits on general decision procedure."},
    ]


def main() -> None:
    config = ChurchConfig()
    themes = church_themes()
    scored = [score_theme(row, config) for row in themes]
    cautions = interpretation_cautions()

    summary = {
        "article": config.article,
        "timestamp_utc": timestamp_utc(),
        "themes_reviewed": len(scored),
        "core_threads": sum(1 for row in scored if row["interpretive_status"] == "core_church_formal_computation_thread"),
        "major_threads": sum(1 for row in scored if row["interpretive_status"] == "major_church_formal_computation_thread"),
        "supporting_threads": sum(1 for row in scored if row["interpretive_status"] == "supporting_church_formal_computation_thread"),
        "mean_formal_score": round(mean(float(row["formal_score"]) for row in scored), 6),
        "cautions": len(cautions),
        "interpretation": "Church should be studied as a bridge between functions, formal calculation, lambda reduction, undecidability, type theory, and programming-language foundations.",
    }

    write_csv(TABLES / "church_themes.csv", themes)
    write_csv(TABLES / "church_formal_computation_map.csv", scored)
    write_csv(TABLES / "interpretation_cautions.csv", cautions)
    write_csv(TABLES / "church_formal_computation_summary.csv", [summary])

    write_json(JSON_DIR / "church_config.json", asdict(config))
    write_json(JSON_DIR / "church_formal_computation_map.json", scored)
    write_json(JSON_DIR / "interpretation_cautions.json", cautions)
    write_json(JSON_DIR / "church_formal_computation_summary.json", summary)

    print("Church formal computation map complete.")
    print(TABLES / "church_formal_computation_summary.csv")


if __name__ == "__main__":
    main()

This workflow turns Church’s legacy into a reproducible interpretive artifact: formalization, function abstraction, symbolic transformation, substitution, reduction, computability, undecidability, type influence, programming relevance, and AI caution are documented together.

Back to top ↑

R Workflow: Formal Computation Diagnostics

The R workflow reads the generated CSV outputs, summarizes Church themes, visualizes dimensions, and writes an additional diagnostic table.

# alonzo_church_lambda_calculus_summary.R
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")
dir.create(tables_dir, recursive = TRUE, showWarnings = FALSE)
dir.create(figures_dir, recursive = TRUE, showWarnings = FALSE)

map_path <- file.path(tables_dir, "church_formal_computation_map.csv")
summary_path <- file.path(tables_dir, "church_formal_computation_summary.csv")

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

church_map <- read.csv(map_path, stringsAsFactors = FALSE)
summary <- read.csv(summary_path, stringsAsFactors = FALSE)

png(file.path(figures_dir, "church_formal_computation_dimensions.png"), width = 1200, height = 850)
score_matrix <- t(as.matrix(church_map[, c("formalization", "functional_abstraction", "symbolic_transformation", "substitution", "reduction", "computability", "undecidability", "type_influence", "programming_relevance", "ai_caution")]))
barplot(score_matrix,
        beside = TRUE,
        names.arg = church_map$theme_id,
        las = 2,
        ylim = c(0, 1),
        ylab = "Interpretive Score",
        main = "Alonzo Church, Lambda Calculus, and Formal Computation")
legend("bottomright",
       legend = rownames(score_matrix),
       cex = 0.68,
       bty = "n")
grid()
dev.off()

png(file.path(figures_dir, "church_formal_score_by_theme.png"), width = 1000, height = 750)
barplot(church_map$formal_score,
        names.arg = church_map$theme_id,
        las = 2,
        ylab = "Formal Computation Score",
        main = "Church Formal Computation Score by Theme")
grid()
dev.off()

r_summary <- data.frame(
  themes_reviewed = summary$themes_reviewed[1],
  core_threads = summary$core_threads[1],
  major_threads = summary$major_threads[1],
  supporting_threads = summary$supporting_threads[1],
  mean_formal_score = summary$mean_formal_score[1],
  cautions = summary$cautions[1],
  diagnostic_note = "Church should be studied as a bridge between functions, formal calculation, lambda reduction, undecidability, type theory, and programming-language foundations."
)

write.csv(r_summary, file.path(tables_dir, "r_church_formal_computation_diagnostic_summary.csv"), row.names = FALSE)
print(r_summary)

The R layer makes the interpretive structure visible: formalization, functional abstraction, symbolic transformation, substitution, reduction, computability, undecidability, type influence, programming relevance, and AI caution can be compared across themes.

Back to top ↑

GitHub Repository

The companion repository contains reproducible workflows, synthetic interpretive data, outputs, calculators, documentation, and multilingual examples for this article.

Back to top ↑

A Practical Method for Studying Church

A careful study of Church asks how functions, formal systems, computability, undecidability, and programming-language foundations fit together.

This method keeps Church’s contribution precise: computation as functions, expressions, and formal transformation.

Back to top ↑

Common Pitfalls

The first pitfall is treating lambda calculus as ordinary algebra. The second is treating it as a hardware model. The third is ignoring variable binding and capture. The fourth is treating the Church-Turing thesis as a simple theorem. The fifth is forgetting that Church’s legacy includes undecidability as well as expressive power.

Church’s work is strongest when its minimalism, rigor, and limits are all kept visible.

Back to top ↑

Why Church Still Matters

Alonzo Church still matters because he gave computation a formal language of functions. Lambda calculus shows that computation is not tied to machines, hardware, or physical motion. It can be modeled as symbolic expression, abstraction, application, substitution, and reduction. This view helped define effective calculability and remains central to programming languages, logic, proof systems, and formal reasoning.

Church also matters because his work reveals limits. The same formal clarity that makes computation powerful also shows that no general method can decide everything. Computation is expressive, but not omnipotent. Formal systems can clarify reasoning, but they must be scoped and interpreted.

For the history of algorithms, Church provides a necessary counterpoint to Turing. Turing makes computation visible as an abstract machine. Church makes computation visible as formal function transformation. Together they show why modern computational reasoning is both powerful and bounded. AI belongs in the toolkit, not in control.

Back to top ↑

Related Articles

• Alan Turing, Computation, and the Machine Model of Reasoning
• John von Neumann, Stored-Program Architecture, and Computational Systems
• Computability and the Limits of Procedure
• Lambda Calculus, Functions, and Formal Computation
• Formal Methods and Machine-Checked Reasoning

Back to top ↑

Further Reading

• Church, A. (1936) ‘An Unsolvable Problem of Elementary Number Theory’. American Journal of Mathematics, 58(2), pp. 345–363.
• Church, A. (1936) ‘A Note on the Entscheidungsproblem’. Journal of Symbolic Logic, 1(1), pp. 40–41.
• Church, A. (1941) The Calculi of Lambda-Conversion. Princeton: Princeton University Press.
• Deutsch, H. (2021) ‘Alonzo Church’. Stanford Encyclopedia of Philosophy.
• Alama, J. (2012) ‘The Lambda Calculus’. Stanford Encyclopedia of Philosophy.
• Copeland, B.J. (1997) ‘The Church-Turing Thesis’. Stanford Encyclopedia of Philosophy.
• Barendregt, H.P. (1984) The Lambda Calculus: Its Syntax and Semantics. Amsterdam: North-Holland.
• Hindley, J.R. and Seldin, J.P. (2008) Lambda-Calculus and Combinators: An Introduction. Cambridge: Cambridge University Press.

Back to top ↑

References

• Alama, J. (2012) ‘The Lambda Calculus’. Stanford Encyclopedia of Philosophy. Available at: https://plato.stanford.edu/entries/lambda-calculus/.
• Barendregt, H.P. (1984) The Lambda Calculus: Its Syntax and Semantics. Amsterdam: North-Holland.
• Church, A. (1936) ‘An Unsolvable Problem of Elementary Number Theory’. American Journal of Mathematics, 58(2), pp. 345–363. Available at: https://www.ics.uci.edu/~lopes/teaching/inf212W12/readings/church.pdf.
• Church, A. (1936) ‘A Note on the Entscheidungsproblem’. Journal of Symbolic Logic, 1(1), pp. 40–41. Available at: https://courses.fit.cvut.cz/MI-VYC/church-a-note-on-the-entscheidungsproblem.pdf.
• Church, A. (1941) The Calculi of Lambda-Conversion. Princeton: Princeton University Press.
• Copeland, B.J. (1997) ‘The Church-Turing Thesis’. Stanford Encyclopedia of Philosophy. Available at: https://plato.stanford.edu/entries/church-turing/.
• Deutsch, H. (2021) ‘Alonzo Church’. Stanford Encyclopedia of Philosophy. Available at: https://plato.stanford.edu/entries/church/.
• Hindley, J.R. and Seldin, J.P. (2008) Lambda-Calculus and Combinators: An Introduction. Cambridge: Cambridge University Press.

Back to top ↑