Timeline for O(n*log(n)) Turing Machine with exactly 1 tape for “equal number of a's and b's in a given word”?
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 8, 2018 at 13:56 | vote | accept | Caffeine | ||
| May 8, 2018 at 10:29 | history | tweeted | twitter.com/StackCompSci/status/993799942182440960 | ||
| May 8, 2018 at 8:57 | answer | added | Yuval Filmus | timeline score: 5 | |
| May 8, 2018 at 8:28 | comment | added | Caffeine | Also, i have only 1 tape = counter will be at the end of the tape. And i have only 1 head which reads\writes | |
| May 8, 2018 at 8:27 | comment | added | Caffeine | But for each character you run to the end of the tape. So the runs will be 1 step, 2 steps,...., n steps. Sum(1 to n) is O(n^2). And that's even without the changes made to the bits of the counter | |
| May 8, 2018 at 8:25 | comment | added | Jake | Not if you represent the count in binary. | |
| May 8, 2018 at 8:25 | comment | added | Caffeine | Keeping a count means writing the bits that represents the counter at the end of the tape and changing it for each a or b (running to the end of tape (=n steps) for each a or b (=n steps) to change the count). This would be O(n^2) steps. If i could keep a counter which operates in O(1) then the whole algorithm would run in O(n) since only 1 pass will be needed. The problem is the implementation of the counter | |
| May 8, 2018 at 8:01 | comment | added | Jake | What if you keep a count or two? How many bits are in a count? How efficiently can increment/decrement a count? | |
| May 8, 2018 at 7:40 | history | asked | Caffeine | CC BY-SA 4.0 |