What “computation” means

You walk up to a metro turnstile. You tap a card. The arms unlock. You push through. The arms lock again. Nobody “thinks” inside that turnstile, yet it makes a decision every time: let this person through, or not.

Now picture three gadgets on your desk:

• A password box that answers “correct” or “wrong”.
• A code editor that underlines your code in red when the brackets don’t match.
• A compiler that says “this program will never stop running” — or does it? Can any program actually say that reliably?

All three read some input and give a yes/no verdict. Theory of Computation (TOC) is the study of exactly this: which yes/no questions can a machine answer, and how much memory does it need to answer them? Some questions need almost no memory. Some need a lot. And — the most surprising fact in all of computer science — some questions cannot be answered by any machine, however powerful.

A machine reads a long line of text, one character at a time, and must answer: “Did the text contain an even number of characters?”

How much does the machine need to remember while reading? (a) every character so far, (b) the exact count so far, or (c) just one tiny fact?

Prediction check

Answer: (c) — one tiny fact. The machine only needs to remember “so far the count is even” or “so far the count is odd”. Each new character flips that fact. At the end, it says yes if the fact is “even”. It never needs the actual number. This is the first big idea of the subject: a machine should remember only what the question needs.

What a “machine” means here

Forget motors and chips. In TOC a machine is any precise, step-by-step procedure that:

1. receives an input — a finite sequence of symbols (characters) such as 1011 or if(x){y};
2. reads it, one symbol at a time, changing its internal mode (what it currently “has in mind”) after each symbol;
3. finishes with a verdict: yes or no.

Saying “yes” is called accepting the input. Saying “no” is called rejecting it.

What “computation” means

Notice the word possibly. A badly behaved procedure might never finish — like a program stuck in an infinite loop. Keep that thought: it becomes the heart of the final phase.

Yes/no questions = decision problems

A question about inputs whose answer is always yes or no is a decision problem. Examples:

• “Is this binary number divisible by 3?”
• “Are the brackets in this code balanced?”
• “Is this word the same read backwards (like racecar)?”
• “Does this program ever stop?”

Why only yes/no? Because almost every other task can be rebuilt from yes/no questions (“what is the sum?” becomes “is the sum’s first digit 1? is the second digit 0? …”). Yes/no questions are the simplest thing to study and they lose almost nothing.

The one thing that separates machines: memory

Every machine we study reads input the same way. What makes one machine stronger than another is how much it can remember, and how it can use that memory. The whole subject is a single story with four chapters:

1. A fixed, finite amount of memory (like the even/odd machine: it can be in only a few modes). Fast, simple, used in text search and lexers.
2. A pile of plates — memory you can add to and remove from, but only at the top. Enough for matching brackets.
3. An endless notebook you can read, write and move around in freely. This is as powerful as any computer that can ever exist.
4. The wall: questions that even the endless notebook cannot answer.

Finite memory, made concrete

“Finite memory” means the machine has a fixed list of modes decided before it sees any input. A machine with 4 modes has 4 modes whether the input has 10 characters or 10 billion. It cannot grow.

So a question is “easy” (finite-memory) if, while reading, you only ever need to know one of a fixed number of facts. Even/odd count: 2 facts. “Has the text contained the letter z yet?”: 2 facts. “Last character seen was a digit?”: 2 facts.

A question is “hard” for finite memory if the needed fact can grow without limit — like “how many more ( than ) have I seen?” That number can be 1, 2, 500, a million… no fixed list of modes can hold every possibility.

Putting it together

• A machine reads a finite input one symbol at a time and ends with yes, no — or never ends.
• Every yes/no question about inputs is a decision problem.
• Machines differ only in memory. Finite memory works exactly when the fact you must carry stays bounded.

A turnstile as a finite-memory machine. Its only memory is which mode it is in. Inputs are coin and push.

          coin                      push
   ┌──────────────┐          ┌──────────────┐
   │              ▼          │              ▼
 ┌─┴──────┐   coin   ┌───────┴─┐   push   ┌────────┐
 │ LOCKED │ ───────► │UNLOCKED │ ───────► │ LOCKED │ (same mode, drawn twice)
 └────────┘          └─────────┘          └────────┘
   push: stays LOCKED          coin: stays UNLOCKED

Trace of the input coin push push coin, starting LOCKED:

read      mode before → mode after
coin      LOCKED      → UNLOCKED
push      UNLOCKED    → LOCKED      (person walked through)
push      LOCKED      → LOCKED      (arms don't move)
coin      LOCKED      → UNLOCKED
end: mode = UNLOCKED.  Question "is it unlocked at the end?"  → YES

And the even/odd machine on abcab:

start EVEN ─a→ ODD ─b→ EVEN ─c→ ODD ─a→ EVEN ─b→ ODD   end: ODD → answer NO (5 is odd)

This lesson set the stage: machines read inputs and say yes or no, and they differ by memory. To talk about inputs, memory and machines precisely, we need a small math toolkit first. Next question: how do we describe a whole collection of inputs (for example, “all inputs this machine says yes to”) in a precise way?

1. MCQ

   Which statement best describes what Theory of Computation studies?

   1. How to make computers run faster
   2. Which yes/no questions machines can answer, and how much memory they need
   3. How to write programs in C
   4. How electricity flows in circuits
2. MSQ

   Which of these can be answered by a machine with a fixed, finite number of modes for every input length?

   1. Does the input contain the letter q?
   2. Is the input length even?
   3. Does the input have more a’s than b’s?
   4. Does the input start with the letter a?
3. NAT

   A machine checks “is the number of characters a multiple of 5?” What is the smallest number of modes it needs?

   Write your answer before opening the key.

4. MCQ

   A procedure is run on an input and keeps running forever. What has it said about the input?

   1. Yes
   2. No
   3. Nothing — it gave no verdict
   4. Both yes and no

• computation
• machine
• input (finite sequence of symbols)
• mode of a machine
• accept (yes) / reject (no)
• decision problem
• finite memory
• bounded vs unbounded fact

1. In TOC, what makes one machine more powerful than another?
   Reveal answer

   The amount of memory it has and how it can use it.
2. What are the two verdicts a machine can give — and what is the third possibility?
   Reveal answer

   Accept (yes) or reject (no). Third: it never finishes, giving no verdict.
3. Can a fixed-mode machine check “equal numbers of ( and )”? Why?
   Reveal answer

   No. It must remember the difference opens − closes, which can grow without limit.
4. Minimum modes to check “length is a multiple of k”?
   Reveal answer

   k (remainders 0 … k−1).

• Fast test for “finite memory is enough”: write down the fact you must carry while reading. If it can take only finitely many values (remainder, last few symbols, yes/no flags) — finite memory works. If it is a count or a comparison that can grow — it doesn’t.