4 ms·
I wonder if this is new. Some weeks ago Nick Drozd, who found a new 4 color, 2 state BLB TM, used this in combination with another optimization (a counter for r
by fjfaase 5y ago
I wonder if this is new. Some weeks ago Nick Drozd, who found a new 4 color, 2 state BLB TM, used this in combination with another optimization (a counter for repeated cells with the same color). This was reported on HN: https://news.ycombinator.com/item?id=29888388 https://news.ycombinator.com/item?id=29888388. To analyze this TM, I made an implementation in C++. (See my home page for the details.)
(Edit: Added name and link to HN article)
- cube2222 5y agoIt's not new, at least not as far as the theory goes. This model is basically how the standard proof goes that pushdown automata with two stacks are equal in power to a Turing Machine. Here's for example a stackexchange answer from 2012 using this: https://cs.stackexchange.com/questions/2832/is-a-push-down-automaton-with-two-stacks-equivalent-to-a-turing-machine https://cs.stackexchange.com/questions/2832/is-a-push-down-a...