undefined | Better HN

0 pointsgeneralizations2y ago0 comments

Oh, I meant formalization as in, this is clearly not either a turing machine or a lambda calculus, but as it appears turing-complete, it must be equivalent, and could benefit from formalization in that computer-science/mathematical sense. Then we outsiders would be able to see what we're looking at.

0 comments

mikewarot2y ago

You could consider a BitGrid to be a giant state machine, given any current set of inputs, and the program loaded into it, it is possible to know exactly what the next state will be. The connectivity turns it into a complex system. The number of possible states is somewhere between 1 and 16^cellcount

I'm not sure that it's possible to compute (in a reasonable amount of time, or maybe ever) the exact number of possible states a bitgrid may have, given its current program.

It's my conjecture that finding this exact number is equivalent to solving the halting problem.

---

Also, any computation in a Bitgrid is an acyclic directed graph. Because there is a delay between cells, you can only effect future states.

j / k navigate · click thread line to collapse