Difference between revisions of "Intuitive Computability"
(Created page with "==Full Title or Meme== What a computer programmer means when she says "I can build that!" ==Context== Alonzo Church ==References== Category: Philosophy") |
|||
| Line 4: | Line 4: | ||
==Context== | ==Context== | ||
Alonzo Church | Alonzo Church | ||
| + | ==Solutions== | ||
| + | Intuitive Computability — The Informal Notion | ||
| + | Before the 1930s, mathematicians and engineers didn’t have a formal definition of what it meant for a function or process to be computable. They relied on an intuitive sense: | ||
| + | “If I can describe a step‑by‑step procedure that a human (or a machine) could follow without ingenuity, then it’s computable.” | ||
| + | |||
| + | This is what we now call effective calculability — the informal, pre‑formalized idea that something can be worked out mechanically. | ||
| + | |||
| + | When a modern programmer says “I can build that!”, she’s often making the same kind of judgment: | ||
| + | |||
| + | She has an internal model of what’s possible with the tools, languages, and hardware at hand. | ||
| + | |||
| + | She mentally sketches an algorithmic path from problem to solution. | ||
| + | |||
| + | She assumes that if the steps are clear and finite, the computer can execute them. | ||
| + | |||
| + | That’s intuitive computability in action — a gut‑level mapping from a problem to a feasible algorithm. | ||
| + | |||
| + | 🔬 Alonzo Church’s Contribution | ||
| + | In 1936, Alonzo Church took that fuzzy, intuitive idea and gave it a precise mathematical form: | ||
| + | |||
| + | λ‑calculus — a formal system for defining and applying functions. | ||
| + | |||
| + | Church’s Thesis (later the Church–Turing Thesis) — the claim that anything effectively calculable (in the intuitive sense) can be computed by a λ‑calculus expression, a Turing machine, or any equivalent formalism2. | ||
| + | |||
| + | This was a bridge between: | ||
| + | |||
| + | The informal “I can build that” intuition. | ||
| + | |||
| + | The formal definition of computability. | ||
| + | The Programmer’s “I Can Build That!” as Computability Check | ||
| + | When a programmer says this, she’s implicitly: | ||
| + | * Recognizing the problem as one that can be expressed in finite, discrete steps. | ||
| + | * Matching it to known computational patterns (sorting, searching, parsing, optimization, etc.). | ||
| + | * Believing that no step requires “magic” — only mechanical execution. | ||
| + | |||
| + | Church’s work tells us: if those steps can be clearly specified, they can be represented in a formal system like λ‑calculus — and therefore computed by a real machine. | ||
| + | |||
| + | Why This Matters | ||
| + | * Limits: Church–Turing reminds us there are problems that feel like they should be solvable but aren’t (e.g., the Halting Problem). | ||
| + | * Power: It also tells us that all general‑purpose programming languages are equivalent in what they can compute — differences are about how easily you can express the solution, not whether it’s possible. | ||
==References== | ==References== | ||
[[Category: Philosophy]] | [[Category: Philosophy]] | ||
Revision as of 11:02, 5 September 2025
Full Title or Meme
What a computer programmer means when she says "I can build that!"
Context
Alonzo Church
Solutions
Intuitive Computability — The Informal Notion Before the 1930s, mathematicians and engineers didn’t have a formal definition of what it meant for a function or process to be computable. They relied on an intuitive sense:
“If I can describe a step‑by‑step procedure that a human (or a machine) could follow without ingenuity, then it’s computable.”
This is what we now call effective calculability — the informal, pre‑formalized idea that something can be worked out mechanically.
When a modern programmer says “I can build that!”, she’s often making the same kind of judgment:
She has an internal model of what’s possible with the tools, languages, and hardware at hand.
She mentally sketches an algorithmic path from problem to solution.
She assumes that if the steps are clear and finite, the computer can execute them.
That’s intuitive computability in action — a gut‑level mapping from a problem to a feasible algorithm.
🔬 Alonzo Church’s Contribution In 1936, Alonzo Church took that fuzzy, intuitive idea and gave it a precise mathematical form:
λ‑calculus — a formal system for defining and applying functions.
Church’s Thesis (later the Church–Turing Thesis) — the claim that anything effectively calculable (in the intuitive sense) can be computed by a λ‑calculus expression, a Turing machine, or any equivalent formalism2.
This was a bridge between:
The informal “I can build that” intuition.
The formal definition of computability. The Programmer’s “I Can Build That!” as Computability Check When a programmer says this, she’s implicitly:
- Recognizing the problem as one that can be expressed in finite, discrete steps.
- Matching it to known computational patterns (sorting, searching, parsing, optimization, etc.).
- Believing that no step requires “magic” — only mechanical execution.
Church’s work tells us: if those steps can be clearly specified, they can be represented in a formal system like λ‑calculus — and therefore computed by a real machine.
Why This Matters
- Limits: Church–Turing reminds us there are problems that feel like they should be solvable but aren’t (e.g., the Halting Problem).
- Power: It also tells us that all general‑purpose programming languages are equivalent in what they can compute — differences are about how easily you can express the solution, not whether it’s possible.
