3 ms·

Yes, I get the idea, but I don't understand how you'd convert an arbitrary TM into a graph. Conversion + coloring is equivalent to running the TM. Coloring runs

by jules 18y ago

Yes, I get the idea, but I don't understand how you'd convert an arbitrary TM into a graph. Conversion + coloring is equivalent to running the TM. Coloring runs in finite time, so a conversion algorithm will sometimes not terminate? > Are you sure? No. > Why? As far as I know, photocopiers shine light through the paper on the drum. Electrical charge is eliminated on those places that get light. Black letters block the light, and the toner gets attracted to the charge on the drum where the letters are. Because light can't go through a mirror, it's equivalent to a black sheet of paper. > Can you prove it from first principles? What do you mean by first principles? > prove that a well-designed photocopier must give a particular result. What do you mean by well-designed? I suppose a perfect copier would produce a mirror. A good photocopier can produce either white or black (depending on which side it measures the light). Maybe this is a mathematical question but I don't get it...

RiderOfGiraffes 18y ago
Re photocopier: I don't want to give away the answer and spoil it for those who may want to think about it, but photocopiers do not shine light through paper. When I say "from first principles" I mean - think about the task accomplished by a photocopier, and the general means by which it does that. Deduce from that what must happen when it photocopies a mirror. And when I say "well-designed", early copiers had some undesirable characteristics which have now been eliminated. I can't think of any more to say without giving away the answer. And to the question of the TM: Part of the assumption is that we have an NP problem, hence we have an algorithm (in the technical sense) to verify an alleged solution. By definition that algorithm must run in polynomial space and time. That means the graph only needs to be polynomial in size. More specifically, for each cell on the tape have a vertex for each possible symbol. Arrange logic gates so that exactly one of them will be "1" and the others will be "0". Now also have a set of vertices for the states, and arrange that exactly one will be "1" with the others "0". Make a copy of this, and connect with gates so that the second copy is forced to be the state of the tape and machine after one step. Repeat as many times as there are steps in the algorithm, which is polynomial. In short, we're not converting an arbitrary TM. For a given instance that needs checking the TM is of finite size and runs for finite time, so the graph to color is finite. If it can't be colored the problem has no solution. If it can be colored, the coloring gives you the answer, appearing at its inputs. Please, ask if there's anything still unclear. It's nice to reactivate the associated mental pathways.
- 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

Re photocopier: I don't want to give away the answer and spoil it for those who may want to think about it, but photocopiers do not shine light through paper. When I say "from first principles" I mean - think about the task accomplished by a photocopier, and the general means by which it does that. Deduce from that what must happen when it photocopies a mirror. And when I say "well-designed", early copiers had some undesirable characteristics which have now been eliminated. I can't think of any more to say without giving away the answer. And to the question of the TM: Part of the assumption is that we have an NP problem, hence we have an algorithm (in the technical sense) to verify an alleged solution. By definition that algorithm must run in polynomial space and time. That means the graph only needs to be polynomial in size. More specifically, for each cell on the tape have a vertex for each possible symbol. Arrange logic gates so that exactly one of them will be "1" and the others will be "0". Now also have a set of vertices for the states, and arrange that exactly one will be "1" with the others "0". Make a copy of this, and connect with gates so that the second copy is forced to be the state of the tape and machine after one step. Repeat as many times as there are steps in the algorithm, which is polynomial. In short, we're not converting an arbitrary TM. For a given instance that needs checking the TM is of finite size and runs for finite time, so the graph to color is finite. If it can't be colored the problem has no solution. If it can be colored, the coloring gives you the answer, appearing at its inputs. Please, ask if there's anything still unclear. It's nice to reactivate the associated mental pathways.

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.