Timeline for reversible Turing machines
Current License: CC BY-SA 2.5
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 11, 2010 at 16:03 | comment | added | Joel David Hamkins | It is easy to prove. Suppose the machine could tell when the finitely many 1s end, and the all-0s start. Let the machine operate, but now change some 0 to 1 very far away, which the machine never looks at in that computation. The computation would behave just the same, since it never sees that cell, but get the wrong answer, since there was a 1 way out there. | |
| May 11, 2010 at 15:49 | comment | added | Łukasz Grabowski | Do you know if the statement "This is not possible if the machine cannot tell when the total input ends (that is, the random stuff beyond the g's)." has been made into a precise theorem with a proof? | |
| May 11, 2010 at 14:09 | comment | added | Joel David Hamkins | I understand your point now about the {0,1,g} example, and I think that this illustrates the difference between what I had called normal input and the situation you are thinking about, where the tape has extra random stuff on it. My algorithm wouldn't work on this example, even with the end-of-input markers and even if there is only finitely much extra stuff, since I need for the machine to be able to tell the entire input string in order to write down the computation history. This is not possible if the machine cannot tell when the total input ends (that is, the random stuff beyond the g's). | |
| May 11, 2010 at 13:59 | comment | added | Joel David Hamkins | ...There is a way of coding more symbols into the {0,1} alphabet, just by operating two-cells-at-once. For example, by grouping them in twos, you really have four symbols: 00 01 10 11. This way, one can still perform computation on input strings, but one should set up the input tape to use only 00 and 01 (interpreted as 0 and 1 respectively) for the input, marked off by 11 at the ends, so that the machine knows when the input has finished. That is, if you set up your input to respect the coding, and then it is as though you have more symbols. | |
| May 11, 2010 at 13:45 | comment | added | Joel David Hamkins | Thanks for accepting my answer. You are right to pay attention to markers for end-of-input. When using just {0,1} as the alphabet, one usually must use unary form for input (that is, the number n represented as n consecutive 1s), rather than thinking of finite strings, since otherwise there is no way to tell when the input has ended. This unary input is what I meant by normal computation, but I notice that your definition of Tapes is more general than that for the starting configuration, and so my answer will not work in that more general setting. But it does work for the usual input form. | |
| May 11, 2010 at 12:44 | vote | accept | Łukasz Grabowski | ||
| May 11, 2010 at 12:43 | comment | added | Łukasz Grabowski | Now it seems to me that the process of copying the word g cannot be made irreversible. The reason I'm interested in this kind of process is because it seems to me taht "preparing an infinite (or a long enough) tape with only 0's" is "expensive thermodynamically" :-). Still, I think I understood something thanks to your answer, so cheers :-). | |
| May 11, 2010 at 12:37 | comment | added | Łukasz Grabowski | Joel, I'm still unhappy, but I admit your answer answers my question :-). Let me informally say why I'm still unhappy. Suppose T' operates on {0,1,g}, where g is certain special symbol, but at the beginning T' is not given a tape with only 0's and the word written on it but rather a tape with a word written between two symbols g, and random entries elsewhere. Starting with the original T one can easily modify it and define T' in such a way that it ignores entries besides the two symbols g and so it accepts the word between two g's iff this word belongs to L. (TBC) | |
| May 11, 2010 at 12:31 | vote | accept | Łukasz Grabowski | ||
| May 11, 2010 at 12:31 | |||||
| May 10, 2010 at 23:11 | comment | added | Joel David Hamkins | Lukasz, in this case, my answer seems to meet all your requirements. I had in mind that my algorithm would use just one tape. In any case, Turing machines with one tape can easily simulate Turing machines with multiple tapes---these computational models are well-known to have equal power. | |
| May 10, 2010 at 19:41 | comment | added | Łukasz Grabowski | 1) My definition requires injectivy on the set $Y=\bigcup ...$, not on the whole set $\text{Tapes} \times B$. $Y$ is precisely the set of configurations which arise in the actual computation. 2) I insist on considering a Turing machine with just one tape. | |
| May 10, 2010 at 12:13 | comment | added | Joel David Hamkins | My solution has only a finite increase in the state space (since the universal machine has only finitely many states), and no increase in the alphabet. Of course, it does use more of the tape, and the computations will take longer time. But the OP may object that my computations are only reversible on the configurations that arise in normal computation, and not necessarily on all possible configurations. | |
| May 10, 2010 at 12:10 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
added 325 characters in body
|
| May 10, 2010 at 12:06 | comment | added | Jacques Carette | I don't think this answers the OP's intended question: he would like a finite increase of the state space (or perhaps the alphabet as well) which allows this. You use the tape to track this, in a clearly unbounded manner. | |
| May 10, 2010 at 12:02 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |