First page Back Continue Last page Overview Graphics
Multiplication
Implement multiplication circuits
- Both unary and binary multiplication
- Unary is core of undecidability proof
- Not based on TMs, but just as with TM simulation, round-trip PUs used to encode finite-state transducers
Multiply: solutions that start with flight sequences “17” and “19”
Divide: solutions that start with flight sequence “17” and end in flight sequence “323”
Factor: solutions that end with flight sequence “323”
Notes:
Here two multiplication circuits are implemented, one unary and one binary. However the unary multiplication circuit does not include the complications necessary for unbounded tape length. These are custom circuits not based on Turing Machines, but that use the same mechanisms to copy information forward through the steps of a computation. The search engine searches over all possible inputs, so its output is a “times table”. To aid interpretation, values have been assigned to fares such that the dollar amount is equal to the product of the 10-cent and 1-cent position (i.e., $21.73 indicates that 21 is 7 times 3 ). Multiplication, division and factoring are the imposition of constraints on different parts of the trip.