Timeline for Proving equivalence of two Turing machines
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 26, 2023 at 2:07 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jul 29, 2023 at 2:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Mar 31, 2023 at 1:07 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 1, 2022 at 1:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Aug 3, 2022 at 0:08 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 4, 2022 at 23:05 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 5, 2021 at 22:05 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Aug 8, 2021 at 9:40 | comment | added | Andrej Bauer | There is no marking of positions, you use new auxiliary states to make sure the machine does the correct sequence of moves. For example, if there is a state $S$ in which the machine wants to move left and transition to state $T$, you insert one new auxiliary state $S_1$ and modify the machine thus: in $S$ move right and transition to $S_1$, in $S_1$ move left and transition to $T$. (Depending on the details of your Turing machines, you might have to insert $S_{1,a}$ for every possible symbol $a$.) | |
| Aug 8, 2021 at 9:37 | comment | added | Andrej Bauer | @Steven: on a half-way tape that extends only to the right, the moves "left, right" might fall off the tape. So I think it's safer to simulate a "left" with "right, left". | |
| Aug 7, 2021 at 21:07 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 9, 2021 at 19:04 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 10, 2020 at 19:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Nov 10, 2020 at 18:37 | answer | added | orlp | timeline score: 1 | |
| Nov 10, 2020 at 17:48 | comment | added | Rika | So basically: If M1 moves to the left, M2 moves 2 lefts however mark the position with ‘ * ‘ transition to a new state at which the machine always moves to the left and then transitions to the original target of the LLL transition and that is the only change? | |
| Nov 10, 2020 at 17:07 | history | edited | Rika | CC BY-SA 4.0 |
added 76 characters in body
|
| Nov 10, 2020 at 17:01 | comment | added | Steven | You can simulate a "right" movement with the movements: right, right, left. You can simulate a "left" movement with the movements: left, right. You can simulate a "stay" movement with the movements (if needed) with the movements: right, right, right, left, left. | |
| Nov 10, 2020 at 16:34 | history | asked | Rika | CC BY-SA 4.0 |