Theory Multitape_Clock_Product
theory Multitape_Clock_Product
imports Multitape_Clock_Interface Multitape_Embedding Multitape_Relabelling
begin
section ‹A machine paired with an exact alarm clock›
text ‹The product keeps a machine ‹N› and a clock ‹D› on disjoint tapes.
It writes the unary input for the clock, then alternates their steps.
A step of ‹N› into its accepting state reaches CAcc, and one into its
rejecting state reaches CRej; a step of the clock into either terminal state
reaches CRej. So the product stops as soon as either factor does: the alarm
bounds every path, accepting or not. Each factor's part of the transition
relation is called its ∗‹arm›. Both arms may step into CRej, which is
why ‹arms_alternate› lets a step into a final state carry either turn
flag. Nothing here asks ‹N› to be deterministic, so the product serves
nondeterministic and deterministic machines alike.›