4 ms·

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.