Intuition The one core ideaThere is a single, universal notion of "following step-by-step rules" — and one simple machine (a paper tape + a moving pencil-tip) can carry out any such procedure that any human or fancier machine could. Everything below is just the vocabulary you need before that sentence means something concrete.
This page is the toolbox for Church-Turing thesis . The parent note throws around symbols like f : N → N μ y S ( x )
N N 0 , 1 , 2 , 3 , …
Picture it. Not as a formula — as an endless row of dots, one per number, marching right forever.
Why the topic needs it. Church–Turing talks about functions on numbers . Before we can say "a function turns numbers into numbers," we need the pile of numbers to turn. That pile is N why a machine may sometimes run forever — there is always a next number to try.
Definition Function and the arrow→ function is a rule that takes an input and gives back one output. The notation f : N → N f → from the input-pile to the output-pile.
Intuition Why "one output"?A rule that gave two different answers for the same input wouldn't be a recipe — you couldn't follow it. A function is exactly a recipe: same input, same output, every time.
Picture it. A box labelled f
Worked example Reading the notation aloudf ( 3 ) = 7 3 f 7 ( )
Why the topic needs it. The whole thesis is a claim about functions : "every computable function is Turing-computable." So "function" is the noun the entire chapter is about.
Definition Partial functionA total function gives an answer for every input. A partial function may, for some inputs, give no answer at all — the rule runs forever and never stops. We say it is undefined there.
Picture it. Same box f loops back on itself forever — no output ever escapes.
Intuition Why we must allow thisReal programs can get stuck in an infinite loop. If our theory only allowed functions that always answer, it would ban programs that hang — but those are real programs! So "computable" must include partial functions. This is exactly why the parent's minimization step (Section 8) matters.
Why the topic needs it. The parent says μ partial functions." Without the word "partial," that sentence is noise.
x x y x = ( x 1 , x 2 , … , x n ) x list of numbers, not just one." The subscripts x 1 , x 2
Common mistake The arrow is not a Turing machine's arrowx nothing to do with → over a letter, one sits between two sets.
::: Over a letter ⇒ ⇒
Why the topic needs it. The base function P i n ( x 1 , … , x n ) = x i x
These are the "obviously computable" starting bricks — so simple no one doubts a machine can do them.
Z Z ( x ) = 0 0 Picture: a box that swallows any number and always spits out a single dot (zero... well, an empty slot).
S S ( x ) = x + 1 next number. Picture: on the number-row of Section 1, S
P i n P i n ( x 1 , … , x n ) = x i n i Picture: n i
Intuition Why exactly these three?They are the smallest possible "moves": make a zero, step up by one, pick an input. From these three atoms plus glue (next section), every computable function on numbers can be built. It's like an alphabet: tiny, boring, but everything is spelled from it.
Why the topic needs it. The parent's derivation-from-scratch literally starts here. Without S S ( a dd ( x , n ))
If you have rules g , h 1 , … , h k f ( x ) = g ( h 1 ( x ) , … , h k ( x ) ) . Plain words: run each helper h i those answers into g
Intuition Why this is allowed"Do this, then do that with the result" is the most basic way humans chain steps. If each step is computable, doing them in sequence is too — a finite pipe of finite steps.
Why the topic needs it. It's closure operation #1 in the parent. It's how small bricks combine into bigger ones.
Definition Primitive recursionTo define f ( x , n ) counting input n f ( x , 0 ) = g ( x ) , f ( x , n + 1 ) = h ( x , n , f ( x , n ) ) . Plain words: you're told the answer at n = 0 g n + 1 n 0 1 2
Picture it. A ladder. Rung 0 h n 0 always finishes .
for loop
"Do the work n + 1 for i in range(n). The number of rungs is fixed in advance by n cannot run forever.
Why the topic needs it. This is closure operation #2, and Example 1 (addition) is a straight primitive recursion. It gives us guaranteed-halting computation.
μ f ( x ) = μ y [ g ( x , y ) = 0 ] = the smallest y that makes g ( x , y ) = 0. Plain words: try y = 0 g 0 y = 1 y = 2 first y g 0 y μ
Intuition Why this one is different — and dangerousPrimitive recursion knew in advance how many steps (n no upper limit : maybe g 0 0 , 1 , 2 , … forever . That is a while loop with no guaranteed exit — and it is precisely what makes some functions partial (Section 3).
= 0 0 = 0
Why the topic needs it. The parent says μ for) up to the full μ for + while) — which equal the Turing-computable functions. See Mu-Recursive Functions .
Definition Turing machine — informalAn endless paper tape divided into cells, a head that reads/writes one cell, a small set of states (its "mood"), and a rulebook: "in this state, seeing this symbol, write that, move left/right, switch to that state." That's the whole machine.
Intuition Why so bare-bones?Precisely because it's so simple, if this can compute a function, no one can accuse the computation of "cheating." It's the humble yardstick every other model is measured against. Deep details live in Turing Machine and Universal Turing Machine .
Why the topic needs it. CTT's whole statement is "computable = Turing -computable." The Turing machine is the formal right-hand side of the thesis.
A yes/no question is decidable if some machine, for every input, halts and correctly answers "yes" or "no." (See Decidability and Recursive Languages .) "Is n
Definition Halting problemThe question "will this program eventually stop, or loop forever, on this input?" The famous result: no machine can answer this for all programs — it is undecidable . See Halting Problem .
Intuition Why put these hereThey are the boundary line CTT draws. Because CTT says every algorithm is some Turing machine, "no Turing machine decides halting" upgrades to "no algorithm at all decides halting." The limit becomes universal.
Primitive recursion for loop
Minimization mu while loop
Read top-to-bottom: counting numbers give us functions; base bricks plus composition plus the two loop-types build the μ
Self-test: can you answer each before revealing?
What does N The counting numbers 0 , 1 , 2 , …
Read f : N → N "f →
What is a partial function and why must "computable" include them? A function undefined on some inputs (runs forever there); real programs can loop, so we can't ban them.
What does x A list of inputs ( x 1 , … , x n )
Name the three base functions and what each does. Zero Z ( x ) = 0 S ( x ) = x + 1 P i n i
What does composition let you do? Chain rules: run helpers h i g
Why does primitive recursion always halt? It's a for loop climbing a ladder of fixed height n 0
Why can μ It's an unbounded while search y = 0 , 1 , 2 , … y
What single ingredient separates μ Minimization μ while).
In one line, what is a Turing machine? A tape, a read/write head, finitely many states, and a rulebook of moves.
Why does undecidability of Halting become "universal" under CTT? CTT equates every algorithm with some Turing machine, so "no TM" means "no algorithm whatsoever."
