Hacker News Reader

Comment by emersonrsantos | Hacker News Reader

More refined version of the classic Digi-Comp II and actually turing-complete, according to the creators.

With its 2 Hz speed per “instruction” (ramps, gears) it’s not super slow. I would love to see a bigger version and a simulator without board limits.

Edit: no one yet proved that the toy is Turing complete, but the creators believe it is because you can build NAND gates.

View on HN

Seems like it shouldn't be too hard to make a Rule 110 cellular automaton (https://en.wikipedia.org/wiki/Rule_110), which is turing complete.

It couldn't be with a limited set of marbles could it?

I think it would be fair to call the system Turing complete if it is theoretically capable of addressing an arbitrary amount of memory. Of course, no physical computer or Turing machine actually has unbounded memory.

> They also make the computer Turing-complete, which means that if the board were big enough, it could do anything a regular computer can do (in theory!).

They do account for limited resources when they make the claim, thankfully.

dont you need some form of looping/iteration/recursion?

I think feeding marbles to it repeatedly constitutes “looping”. Think of them as clock pulses going through a CPU. If you want to signal that the computation is finished, you just direct the marble to a bucket (interceptor) instead of to the bottom.

If you built a conveyor to automatically push marbles from the bottom back to the top, then you would have a slow but functional automatic computer.

Reply on news.ycombinator.com