3 ms·

> prove that a well-designed photocopier must give a particular result. Yes, that was stupid of me (you can copy books too after all). When you place an objec

by jules 18y ago

> prove that a well-designed photocopier must give a particular result. Yes, that was stupid of me (you can copy books too after all). When you place an object on a photocopier its goal is to make an object that has the same optical properties as the original. So the copier will scan it with light to determine how it reacts. Then it will produce an object that reacts in the same way. So the result should also be a mirror. > Please, ask if there's anything still unclear. It's nice to reactivate the associated mental pathways. The numbers A and B that are the input to the algorithm that checks if they multiply to N can't be arbitrary size, because then we'd need an infinite graph to represent them. So it's important that 1<A<N and 1<B<N. What you're saying about the TM is that if you have a TM and a number K you can create a graph that will execute the first K steps of the TM. And because checking is polynomial in N you can make K big enough to execute the algorithm, but still polynomial in N. I don't understand exactly how you'd connect state+tape K with state+tape K+1 so that state K+1 is forced to be the right state. You'd need a giant switch statement of the program counter and then connect the states and tape cells to the next state+tape through the results of the giant switch. But I'm not sure why the resulting graph is still polynomial in N.

RiderOfGiraffes 18y ago
Copier: But a copier produces a piece of paper, so that can't be a mirror. So what does it produce, and why? > The numbers A and B that are the input to the algorithm that checks if they multiply to N can't be arbitrary size, because then we'd need an infinite graph to represent them. So it's important that 1<A<N and 1<B<N. Yes > What you're saying about the TM is that if you have a TM and a number K you can create a graph that will execute the first K steps of the TM. And because checking is polynomial in N you can make K big enough to execute the algorithm, but still polynomial in N. Exactly. > But I'm not sure why the resulting graph is still polynomial in N. The next state of the machine is a combination of the current symbol and the previous state, so that's just a big collection of ANDs and ORs and NOTs and so forth. Each tape cell is the same as the previous, unless it was the active cell in the previous state, and then it's a copy of the symbol that the state machine specifies. This will be a very, very big graph, because each cell is a combination of all the previous, but that's still "only" quadratic. It's all still polynomial. You might want to sketch a very small TM that will only take a few steps and only use a small amount of tape. Then write the logical expression for one tape cell in one step as a combination of the cells in the previous step and the state. Then do the same for the state itself.

by jules 18y ago

RiderOfGiraffes 18y ago

Copier: But a copier produces a piece of paper, so that can't be a mirror. So what does it produce, and why? > The numbers A and B that are the input to the algorithm that checks if they multiply to N can't be arbitrary size, because then we'd need an infinite graph to represent them. So it's important that 1<A<N and 1<B<N. Yes > What you're saying about the TM is that if you have a TM and a number K you can create a graph that will execute the first K steps of the TM. And because checking is polynomial in N you can make K big enough to execute the algorithm, but still polynomial in N. Exactly. > But I'm not sure why the resulting graph is still polynomial in N. The next state of the machine is a combination of the current symbol and the previous state, so that's just a big collection of ANDs and ORs and NOTs and so forth. Each tape cell is the same as the previous, unless it was the active cell in the previous state, and then it's a copy of the symbol that the state machine specifies. This will be a very, very big graph, because each cell is a combination of all the previous, but that's still "only" quadratic. It's all still polynomial. You might want to sketch a very small TM that will only take a few steps and only use a small amount of tape. Then write the logical expression for one tape cell in one step as a combination of the cells in the previous step and the state. Then do the same for the state itself.