3 ms·
> With inputs and outputs, one could conceptually write and run any software in it. IO is major caveat though. And there is also real-time to consider. I've b
by zokier 4y ago
> With inputs and outputs, one could conceptually write and run any software in it.
IO is major caveat though. And there is also real-time to consider.
I've been long wondering if we should define more interesting computer models in addition to Turing machines. Games make interesting milestones as an example; you could define a system to be e.g. "Tetris-complete" if you could run a playable version of tetris on it, or more advanced would be "Doom-complete" and simpler could be "Chess-complete" or "Zork-complete". Each model would imply something about not just pure computation, but the practical capabilities in terms of inputs and outputs and also something about performance. Of course it doesn't need to be games, you could use anything as a basis for a model.
- werds 4y agohas anyone run Doom on it yet?
- WastingMyTime89 4y agoAny machine which is Turing complete is Tetris-complete and all the other -complete you list. At the end, all of it is just binary values somewhere and trapping instructions which you can perfectly run on anything Turing-complete.
- zokier 4y ago"receive keyboard events" or "draw pixels on screen" are not properties that arbitrary turing machine has. So it is meaningful to distinguish systems that have those properties (and/or others) from systems that do not. Paradoxically computation is actually just small part of what computers do.
- systoll 4y agoTuring initially distinguishes between ‘automatic machines’ which do not receive input, and ‘choice machines’, which do. It then describes the latter in terms of the former. It only talks about binary choices, but keyboards are just methods for sending a few of those at once. If you don’t abstract away that kind of stuff, it’s not obvious why you’re doing any generalisation at all. Tetris.app on my phone cannot read from a game boy cartridge, or speak to a joystick or arcade cabinet CRT screen - is it Tetris complete?
- JohnFen 4y ago"receive keyboard events" or "draw pixels on screen" are higher-level actions that are the result of the same computations that are used for everything else.
- deleted 4y ago[deleted]
- lisper 4y ago> IO is major caveat though. And there is also real-time to consider. I think you're missing the point here. No one would use Conway's Life to do anything practical (at least no sane person would). The point of this is to serve as a visceral illustration of the fact that computational completeness can emerge from very simple mechanisms.
- dom111 4y agoRelevant: Build a working game of Tetris in Conway's Game of Life: https://codegolf.stackexchange.com/q/11880/9365 https://codegolf.stackexchange.com/q/11880/9365 You may already have been aware but sharing in case others aren't!
- FartyMcFarter 4y ago> IO is major caveat though. Why? It would seem very simple to implement IO in game of life - simply allow the user to change the content of a number of cells dedicated to input. If you think about it, that's the same thing we do with keyboards and mice at some level.