Timeline for Turing machine that checks whether a given string is an output of a given machine and input
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 12, 2021 at 23:41 | vote | accept | Anguepa | ||
| Feb 12, 2021 at 23:41 | comment | added | Anguepa | I think I got it, thank you! | |
| Feb 12, 2021 at 23:09 | comment | added | Steven | $T_M$ is just a Turing machine that behaves exactly like $M$ until $M$ returns, and then does some more things (i.e., it erases the tape and writes a single "0"). A description of $T_M$ can be derived from a description for $M$. Alternatively, a $T_M$ can "execute" (simulate) $M$ directly from its description. See Universal Turing Machine for the details. | |
| Feb 12, 2021 at 23:02 | comment | added | Anguepa | I'm afraid I'm a mathematician that knows very little about computability. What exactly does it mean that it "simulates" M? | |
| Feb 12, 2021 at 22:28 | history | answered | Steven | CC BY-SA 4.0 |