Week 5: Turing machines

Week 5 · 2 October 2026 · Data Structures (数据结构), Tsinghua University · XuetangX

Back after a two-week gap. Mid-Autumn Festival meant no class on the 25th.

1. What I worked on

绪论 B2: the Turing machine model and a worked example. Two videos, then I traced the example on paper myself.

2. What was challenging, and how I handled it

Tracing the B2-2 example: I was reading the transition table top-to-bottom like code, but it’s actually a lookup table. You find your (state, character) pair and read off what to do. Once I figured that out the rest of the trace went fine. I also spent the first few minutes reviewing week 3 notes so I didn’t start cold after the break.

The bigger question, why study Turing machines at all, clicked by the end. It defines what “computable” means, which matters when the course starts asking whether a problem is even solvable.

3. How well I ran my own learning

Self-score: 100

I traced the example on paper, caught my own mistake with the transition table, and reviewed previous notes before starting. Also looked ahead at what’s next (RAM model, big-O) to have context.

4. What I’ll do differently next session

Keep reviewing previous notes before each session. It made a clear difference today.

Evidence

Paper trace of the B2-2 Turing machine example.