Timeline for Complexity of Turing Machine behavior
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 5, 2016 at 14:00 | comment | added | Joseph O'Rourke | @Yakk: Yes, I think somehow a trace of execution must be involved, rather than just looking at input & output. | |
| May 5, 2016 at 13:54 | comment | added | Yakk | @JosephO'Rourke Then the TM that looks at the symbol, and if it sees 1 moves right, and if it sees empty it halts and accepts, and if it sees 2 it halts and rejects, is arguably more complex under that metric: feed it a tape with a google-plex 1s on it and and it runs longer than the TM in the OP. I doubt that is what you want. You might want something about the max ratio between bits used to describe the tape and the number of steps the TM runs? | |
| May 5, 2016 at 10:25 | comment | added | Joseph O'Rourke | @GerryMyerson: Good question. It seems natural to me to take the max,its worst behavior. So: really complex. | |
| May 5, 2016 at 3:02 | comment | added | Gerry Myerson | In that case, Joseph, do you want to say that machine is really complex, since it's really complex on the empty tape? or, do you want to say it's really simple, since it does something really simple on every possible input but one? | |
| May 5, 2016 at 1:01 | comment | added | Joseph O'Rourke | Thanks. But suppose a TM only exhibits complex behavior on the empty tape, $n=0$. Otherwise it just halts immediately. | |
| May 5, 2016 at 0:56 | history | answered | Bjørn Kjos-Hanssen | CC BY-SA 3.0 |