Timeline for What is Finite Automata Bowl?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 30, 2014 at 22:34 | comment | added | Joey Eremondi | Riiight, I forgot that a 2-counter machine was Turing Complete. I was getting them confused with Reversal-bounded counter machines, which I've done a bunch of research on. | |
| Mar 30, 2014 at 22:16 | comment | added | babou | It is just a counter machnie, but with several counters, one per bowl symbol. And 2 counters are enough to simulate a Turing machine. The trick is that the stack is mimicked by a single integer in unary notation. Try to read the proof .. then ask again if something is not clear. But look at step 2 of the proof in wikipedia. - - - It is a nice encoding proof. | |
| Mar 30, 2014 at 22:11 | comment | added | Joey Eremondi | I don't quite fully understand. If a bowl automaton is just a counter machine, then it shouldn't be able to accept all CF languages. How would it accept $\{w w^R | w \in \Sigma^* \}$? ($w^R$ is $w$ reversed.) | |
| Mar 30, 2014 at 22:06 | history | edited | babou | CC BY-SA 3.0 |
added 403 characters in body
|
| Mar 30, 2014 at 20:50 | history | edited | babou | CC BY-SA 3.0 |
plugged in a lot more details
|
| Mar 30, 2014 at 17:58 | history | answered | babou | CC BY-SA 3.0 |