4 ms·
> Do we run into the limits of undecidability? For this particular canvas, no, as the canvas is finite. Given enough time or space we can exhaust all states o
by drx 13y ago
> Do we run into the limits of undecidability?
For this particular canvas, no, as the canvas is finite.
Given enough time or space we can exhaust all states of the canvas and catch cycles. This applies to any finite canvas.
I would guess these are equivalent to regular languages because of the finite state. You can treat the different canvas states as states of a finite automaton. A finite automaton is a canvas turing machine by ignoring the canvas.
- taliesinb 13y agoYes, I'm quite aware of this. Not to be rude or anything, but it is kinda obvious if you've thought at all finite computational systems.
- drx 13y agoIt is obvious, yeah. I wasn't implying you didn't know it was or anything, just explaining the first sentence to someone who might not have studied complexity theory.
- taliesinb 13y agoYou're right, that was actually a really good explanation. I'm sorry, I misinterpreted your comment! Retroactively upvoted, for what it is worth.