Turing Tumble Community

CS Algorithms (like DFS)?

I’m working through some CS algorithms, and I’m wondering about implementing them on the Turing Tumble board.

Has anyone ever tried to implement something like depth-first search on the Turing Tumble board?

By my understanding, it should be (theoretically) achievable since the board is Turing-complete. I’m wondering if there’s enough space on the board, I guess.

Something like DFS would be far too complex to achieve on the standard board. And, likely would require enormous space on the simulators as well. I can only begin to imagine all of the pieces you’d need to build, and none are obvious. First, you’d have to decide how to encode a graph for input. This would involve encoding a list of vertices, and edges (pairs of vertices). Suppose you’ve done that. Next you’d have to have some working storage area to keep track of which vertices have been visited, which not. You’d need to have a way to find, given a vertex, what its neighbors were. You’d need to have implemented a stack for storing vertices. These are just a few of the pieces. Really, this problem seems fairly daunting (to me at least).

1 Like