8
$\begingroup$

Over the last couple years, I built a mechanical computer powered by marbles and made a game out of it. It's similar to the old Digi-Comp II, except for two key differences:

  1. Parts are repositionable on the board.
  2. You can connect multiple 'bits' together using gears. When one of these bits is flipped, it flips the other bits connected to it.

The above link describes how it works. My question is, what are its theoretical limitations? My theoretical computing background is weak, so please ELI5.

edit: I'm not interested in the obvious limitations: speed (not going to win any races there...), board size, or # of marbles. I'm more interested in its theoretical limitations. Maybe it would help to split it into two questions:

  1. How can it be proven (or disproven) to be Turing-complete?
  2. If more than 3 gear bits are connected together, the friction becomes too great for a marble to turn all of them at once. Does that create additional limitations?

Thanks - I'm really excited to read your answers! I've been thinking about this for a long time.

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ Do you want to consider an idealized model (infinite grid size, infinitely many marbles), or the specific machine at hand? Looking at the melagne of tags you chose, can you narrow down which questions you want to address? What can be computed? How fast can things be computed? What questions about architecture do you have in mind? $\endgroup$
    – Raphael ♦
    May 6 '17 at 8:03
  • 1
    $\begingroup$ The easiest way to narrow down the capabilities of your model is to answer these questions. 1) What are input and output? 2) Which logical gates can you model? I'm asking 2) because it's clear that you don't have a universal computer there; every board configuration is a fixed program, and that corresponds closely to circuits. So, if you can simulate any complete set of gates (e.g. NAND gates), you have a Turing-complete model (assuming infinite everythings). Since you don't have any static component with two inputs and a single output, I don't see immediately what's going on, though. $\endgroup$
    – Raphael ♦
    May 6 '17 at 8:09
  • 2
    $\begingroup$ That said, interesting project! Please let us know in Computer Science Chat when it launches. $\endgroup$
    – Raphael ♦
    May 6 '17 at 8:09
  • 3
    $\begingroup$ In the video, you say: if you make a board big enough, it can do what any computer can do. Well, yes and no: given a computer, you can (theoretically) build a big enough board, but given a board, you can build a computer that needs a bigger board - and that means your boards aren't Turing complete. Turing completeness requires operating on arbitrarily large memory, something your boards cannot do. Every Turing machine is the limit of an infinite series of finite-tape Turing machines, but that doesn't make finite-tape Turing machines Turing complete. $\endgroup$
    – reinierpost
    May 6 '17 at 22:59
  • 2
    $\begingroup$ If you make enlarging a board part of the machine's operation, they do become Turing complete. $\endgroup$
    – reinierpost
    May 6 '17 at 23:02
3
$\begingroup$

What you have right now is a concrete computer. We cannot compare it to a computational model until it is properly formalized.

My intuition is that the board could be modeled as a dataflow architecture. Computational models conceived according to this paradigm can be Turing-complete, but (as was said in the comments) no concrete computer will ever be Turing-equivalent, and I don't think you should worry about this. All real computers are just (imperfect) working metaphors of formal computational models.

Should you come around to the idea of more closely imitating a Turing-equivalent dataflow machine, there are a few issues that could be addressed in order to "strengthen the metaphor", so to speak. Introducing cycles and composition of machines would be the two most important things, in my opinion, but I think your machine is already pretty amazing. It serves its purpose very well, and these "improvements" could sacrifice its usability.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks! And very helpful! I didn't know about the distinction between dataflow architecture and, say, Von Neumann architecture before. I just imagined that, if the board were bigger, a Von Neumann architecture could be built. Any chance you could offer a definition or a link to what you mean by "cycles" and "composition"? $\endgroup$
    – Paul Boswell
    May 8 '17 at 18:53
  • $\begingroup$ For cycles, imagine that there is a way to send the marbles back up, to the start or to some intermediate memory in the middle. That would enable you to compute some kinds of primitive recursive functions. Composition of machines is similar to composition of functions, imagine that you could plug the output of one board into the input of others. $\endgroup$
    – André Souza Lemos
    May 8 '17 at 19:05
  • $\begingroup$ A von Neumann computer is a big cycle. $\endgroup$
    – André Souza Lemos
    May 8 '17 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.