What Pinball Games Are Turing Machines?


I got to thinking about Turing machines. This is the conceptual model for basically all computers. The classic concept is to imagine a string of cells. In each cell is some symbol. It’s gone over by some device that follows some rule about whether and how to change the symbol. We have other rules that let us move the machine from one cell to the next. This doesn’t sound like much. But it’s enough. We can imagine all software to be some sufficiently involved bit of work on a string of cells and changing (or not) the symbols in those cells.

We don’t normally do this, because it’s too much tedious work. But we know we could go back to this if we truly must. A proper Turing machine has infinitely many cells, which no actual computer does, owing to the high cost of memory chips and the limited electricity budget. We can pretend that “a large enough number of cells” is good enough; it often is. And it turns out any one Turing machine can be used to simulate another Turing machine. This requires us to not care about how long it takes to do something, but that’s all right. Conceptually, we don’t care.

And I specifically got wondering what was the first pinball machine to be a Turing machine. I’m sure that modern pinball machines are, since there have been computers of some kind in pinball machines since the mid-1970s. So that’s a boring question. My question is: were there earlier pinball machines that satisfy the requirements of a Turing machine?

My gut tells me there must be. This is mostly because it’s surprisingly hard not to create a Turing machine. If you hang around near mathematics or computer science people you’ll occasionally run across things like where someone created a computer inside a game like Minecraft. It’s possible to create a Turing machine using the elements of the game. The number of things that are Turing-complete, as they say, is surprising. CSS version 3, a rule system for how to dress up content on a web site, turns out to be Turing-complete (if you make some reasonable extra suppositions). Magic: The Gathering cards are, too. So you could set up a game of Magic: the Gathering which simulated a game of Minecraft which itself simulated the styling rules of a web page. Note the “you” in that sentence.

That’s not proof, though. But I feel pretty good about supposing that some must be. Pinball machines consist, at heart, of a bunch of switches which are activated or not by whether a ball rolls over them. They can store a bit of information: a ball can be locked in a scoop, or kicked out of the scoop as need be. Points can be tallied on the scoring reel. The number of balls a player gets to plunge can be increased — or decreased — based on things that happen on the playfield. This feels to me like it’s got to be a Turing-complete scheme.

So I suspect that the layout of a pinball game, and the various ways to store a bit of information, with (presumably) perfect ball-flipping and table-nudging skills, should make it possible to make a Turing machine. (There ought not be a human in the loop, but I’m supposing that we could replace the person with a mechanism that flips or nudges at the right times or when the ball is in the right place.) I’m wanting for proof, though, and I leave the question here to tease people who’re better than I am at this field of mathematics and computer science.

And I’m curious when the first game that was so capable was made. The very earliest games were like large tabletop versions of those disappointing car toys, the tiny transparent-plastic things with a ball bearing you shoot into one of a series of scoops. Eventually, tilt mechanisms were added, and scoring reels, and then flippers, and then the chance to lock balls. Each changed what the games could do. Did it reach the level of complexity I think it did? I’d like to know.

Yes, this means that I believe it would be theoretically possible to play a pinball game that itself simulated the Pinball Arcade program simulating another pinball game. If this prospect does not delight you then I do not know that we can hope to ever understand one another.

Advertisements

Author: Joseph Nebus

I was born 198 years to the day after Johnny Appleseed. The differences between us do not end there.

4 thoughts on “What Pinball Games Are Turing Machines?”

    1. I’m getting pretty far outside my competence to talk about a problem like that. It really calls on the expertise of the philosophy community to work out well.

      My poorly-considered thoughts about it run along these lines, though. Suppose our universe is a simulation run for whatever purpose in the super-universe. If there is no possible way for us to detect the super-universe’s existence, or to demonstrate that it is affecting our universe, then it’s hard to see what the difference is between the status of the simulated universe and whatever the universe being real might mean.

      But suppose that there is a super-universe. Then it’s hard to see what arguments for our universe being a simulation would not also apply to our super-universe; why shouldn’t it be a simulation in a super-super-universe? But then why wouldn’t that be a simulation in a super-super-super-universe? And so on to an infinite regression of universes simulated within more computationally powerful universes.

      That’s nothing conclusive, certainly. There’s no reason we can’t have an infinite regression like that. It feels wasteful of existence, somehow. But it also suggests there’s no point at which any entity in any of the super-(etc)-universes could be confident they were in reality. So either the infinite stack of simulations is wrong or there’s no such thing as “real”. Neither seems quite satisfying.

      I expect the professionals have better reasoning than mine, though. And it might be something that produces useful insights even if it can’t be resolved, akin to Zeno’s Paradoxes.

      Like

  1. The thing with all those provable Turing machines is that they have dynamic and conceptually-unbounded amounts of storage space (Minecraft levels grow, Magic decks grow, etc.), whereas purely-mechanical pinball machines only have a finite amount of state. Which is to say that they are at best a finite state machine. I mean unless you want to go down the rabbit hole of considering every possible physical position of the ball to be a different state, in which case all you need for a Turing machine (given perfect nudge mechanics etc.) is a ball.

    Like

    1. This is true, although I take a forgiving view of storage space. If we can imagine a Magic deck growing as large as needed for the problem we’re working, why can’t we imagine a Pop-A-Card that has a six- or seven- or even 10100-digit score reel? (Taking the score reel to be how the state is stored.) At least it seems to me if someone can keep getting all this tape for their classical Turing machine then we can hook another reel up.

      Like

Please Write Something Good

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s