- Section 5.2
- Parts of proof, esp 3 - 7?
- Tiles work by generating sequences of configurations on top and bottom, with bottom
one configuration ahead of top
- Tiles constructed so that using top to match part of one configuration from bottom inserts corresponding
part of next configuration into bottom
- Tiles constructed so that using top to match part of one configuration from bottom inserts corresponding
part of next configuration into bottom
- Part 1 defines 1st tile so it puts 1st configuration on bottom
- Part 2 simulates writes to tape with move right
- Part 3 simulates writes to tape with move left
- Part 4 copies tape symbols from one configuration to next
- Part 5 copies end-of-configuration markers
- Part 6 consumes tape symbol to clean up at end
- Part 7 “end cap”
- Example: construct tiles for simple machine
- Finish Post Correspondence Problem
- Before class: try to build the rest of the tiles for the example above