4 ms·

It is the simplest possible computer which can actually be built.

by goto11 7y ago

mitchtbaum 7y ago
They don't look so simple tonight.
- TuringTest 7y ago
  That should make you think about the complexity of all other possible computers
- fnrslvr 7y ago
  You're reading a paper that analyzes the capabilities of a particular highly-constrained subclass of Turing machines. Actual research findings aren't necessarily going to be simple just because the model of computation being studied is simple. (Although a similar investigation into the capabilities of, e.g., a similarly constrained subset of Python, would probably tend to be a whole lot more lengthy and arduous.) The parent's point is that the Turing machine model of computation admits a very concise definition -- roughly a page depending on brevity and formatting. An industrially viable programming language or hardware architecture typically requires a standard spanning hundreds of pages to define.
- bspammer 7y ago
  There are plenty of visualizers out there to help out e.g. http://turingmachine.io/ http://turingmachine.io/ The simplest way I can describe them without any maths is that at any point in time they have two inputs, and three outputs. The inputs: * The current "state" of the machine, which is usually shown as a letter - there are a finite number of states the machine can be in, but this number can be as big as you like. * The value currently being pointed at on the tape. The possible values are again finite, but can be as big as you like. The outputs: * A new value to write on the tape. * A new state to be in. * Whether to shift the tape left or right. If you choose your mappings from inputs to outputs carefully, this machine can solve literally every problem your desktop computer can solve. I'd call that pretty amazing.
- arethuza 7y ago
  If you consider the actual complexity of any computer that has actually been built then a TM is, by comparison, very simple.
ncmncm 7y ago
No. It is the simplest that they could think up at the time. Much simpler ones have been invented since. Conway's game of Life is simpler, and universal. People have invented probably hundreds simpler than it. TM gets pride of place as the first, and for no other reason.

It is the simplest possible computer which can actually be built.

by goto11 7y ago

It is the simplest possible computer which can actually be built.

mitchtbaum 7y ago

They don't look so simple tonight.

TuringTest 7y ago
That should make you think about the complexity of all other possible computers
fnrslvr 7y ago
You're reading a paper that analyzes the capabilities of a particular highly-constrained subclass of Turing machines. Actual research findings aren't necessarily going to be simple just because the model of computation being studied is simple. (Although a similar investigation into the capabilities of, e.g., a similarly constrained subset of Python, would probably tend to be a whole lot more lengthy and arduous.) The parent's point is that the Turing machine model of computation admits a very concise definition -- roughly a page depending on brevity and formatting. An industrially viable programming language or hardware architecture typically requires a standard spanning hundreds of pages to define.
bspammer 7y ago
There are plenty of visualizers out there to help out e.g. http://turingmachine.io/ http://turingmachine.io/ The simplest way I can describe them without any maths is that at any point in time they have two inputs, and three outputs. The inputs: * The current "state" of the machine, which is usually shown as a letter - there are a finite number of states the machine can be in, but this number can be as big as you like. * The value currently being pointed at on the tape. The possible values are again finite, but can be as big as you like. The outputs: * A new value to write on the tape. * A new state to be in. * Whether to shift the tape left or right. If you choose your mappings from inputs to outputs carefully, this machine can solve literally every problem your desktop computer can solve. I'd call that pretty amazing.
arethuza 7y ago
If you consider the actual complexity of any computer that has actually been built then a TM is, by comparison, very simple.

ncmncm 7y ago

No. It is the simplest that they could think up at the time. Much simpler ones have been invented since. Conway's game of Life is simpler, and universal. People have invented probably hundreds simpler than it. TM gets pride of place as the first, and for no other reason.