Intuition The one core ideaA Turing Machine reading an input can do three things — accept , reject , or run forever — and that third option splits problems into "we can always answer" versus "we can only ever confirm a yes." Everything in this topic is bookkeeping about which strings a machine says yes to, and whether it always stops .
Before you can read the parent note, you must be able to read every squiggle it uses without pausing. This page introduces them one at a time , each with a picture and a reason it exists. Nothing later uses a symbol from earlier that you have not already seen defined.
Definition Symbol and alphabetΣ alphabet is a finite bag of allowed characters. We name it with the Greek capital letter Σ symbol .
Picture it as a small box of fridge-magnet letters. If the box holds only 0 1 Σ = { 0 , 1 }
Why does the topic need Σ Σ
A string is a finite row of symbols laid left-to-right, e.g. 0110 ε length , written ∣ w ∣ w ∣0110∣ = 4 ∣ ε ∣ = 0
Definition The Kleene starΣ ∗ Σ ∗ all possible strings you can build from Σ every length including zero.
Picture an endless shelf: on shelf 0 sits only ε 0 1 00 , 01 , 10 , 11
Why the star? The topic constantly needs to talk about "any input whatsoever." Σ ∗ infinite even though Σ
Intuition Why finite alphabet but infiniteΣ ∗
∈ ∈ / w ∈ L w L w L w ∈ / L w not in L L w ∈ L w inside the fence; w ∈ / L outside .
⊆ ⊊ A ⊆ B A subset of B A B A ⊊ B proper subset) adds "…and B A A strictly smaller.
Why does the topic need ⊊ Decidable ⊊ Recognizable but some recognizable languages are not decidable. The little slash on ⊊ not equal.
L language L L ⊆ Σ ∗
Here is the mental leap the topic depends on. A yes/no problem ("does DFA B w language : put every input whose honest answer is "yes" inside the fence, and everything else outside .
Intuition Why turn problems into setsOnce a problem is a set of strings, "can a computer solve it?" becomes the crisp question "can a machine sort every string into inside-fence or outside-fence?" We traded a fuzzy word ("solve") for a precise one (membership testing). That trade is the founding move of the whole subject.
L L L L not in L L = Σ ∗ ∖ L ∖ one of L L
Why is L L iff both L L and its complement together . Without the bar you cannot even write it down.
L Why it feels right: "not in L The fix: L L M w L M not accept w Σ ∗
Definition Turing MachineM M Turing Machine — the simplest complete model of "any computer." Feed it a string w accepts , rejects , or loops (never stops).
Picture a robot reading a paper tape one cell at a time, allowed to rewrite cells and move left or right, following a fixed rulebook.
Definition Encoding brackets⟨ ⋅ ⟩ ⟨ M ⟩ M fed to another machine as input. Likewise ⟨ B , w ⟩ B w
Why does the topic need ⟨ ⟩ machines examining machines — e.g. "⟨ M , w ⟩ M w inside a language (a set of strings) if you first turn the machine into a string. The Universal Turing Machine is exactly the robot that reads these encodings.
Definition Accept · Reject · Loop
Accept : M Reject : M Loop : M
Intuition Why the "loop" corridor changes everythingGreen and red are both final answers . The endless corridor is not "no" — it is no answer . Crucially, while watching, you cannot tell "still working, almost done" from "stuck forever." This single blind spot is what separates a machine that decides (never uses the corridor) from one that only recognizes (may use it on non-members). Every theorem in the parent note traces back to this picture.
Definition Iff — the double arrow⟺ P ⟺ Q P if and only if Q always both on or both off.
Proving an ⟺ both ways (⇒ ⇐
Definition Closed under an operationA class of languages is closed under an operation if applying that operation to members always lands you back inside the class. Picture a room where a certain machine (say "take the complement") never lets you walk out the door — you always end up back in the room.
The topic asks: is the decidable class closed under complement? (Yes.) Is the recognizable class? (No.) Answering needs the bar L
Language L a set of strings
Three outcomes accept reject loop
Decidable strictly inside Recognizable
Decidability topic 4.6.17
Every arrow says "you need the left box before the right box makes sense." The two boxes that feed straight into the topic — proper subset and the loop outcome — are the ones the parent note leans on hardest.
Cover the right side and test yourself. If any answer is fuzzy, re-read that section.
What is Σ A finite bag of allowed symbols; a machine can only read characters it was built for, so we fix the alphabet first.
What does Σ ∗ All strings of every length (including ε Σ Σ
Write the meaning of w ∈ L The string w L
What does ⊊ ⊆ "Strictly smaller" — everything in the left set is in the right set, and the right set has at least one extra element.
A yes/no problem becomes a language how? Collect every input whose honest answer is "yes" into the language; all other inputs stay outside.
What is L L L Everything in Σ ∗ L
Why do we need the encoding ⟨ M ⟩ To turn a machine into a string so it can be an input to another machine, letting languages contain machines.
Name the three things a Turing Machine can do on an input. Accept (halt yes), reject (halt no), or loop (never halt).
Why is "loop" different from "reject"? Reject is a final "no"; loop gives no answer at all, and you cannot tell it apart from "still working."
What does it take to prove a statement of the form P ⟺ Q Prove both directions: P ⇒ Q Q ⇒ P
