News for hackers. Stuff that matters.
Re:The Power of One-State Turing Machines (2018) by goto11 on Saturday November 23, 2019 @04:54AM (#21613327)
It is the simplest possible computer which can actually be built.
Re:The Power of One-State Turing Machines (2018) by ncmncm on Saturday November 23, 2019 @01:38PM (#21615661)
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.

Re:The Power of One-State Turing Machines (2018) by mitchtbaum on Saturday November 23, 2019 @05:01AM (#21613345)
They don't look so simple tonight.
Re:The Power of One-State Turing Machines (2018) by bspammer on Saturday November 23, 2019 @07:47AM (#21613847)
There are plenty of visualizers out there to help out e.g. 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.

Re:The Power of One-State Turing Machines (2018) by fnrslvr on Saturday November 23, 2019 @07:20AM (#21613759)
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.

Re:The Power of One-State Turing Machines (2018) by TuringTest on Saturday November 23, 2019 @06:08AM (#21613541)
That should make you think about the complexity of all other possible computers
Re:The Power of One-State Turing Machines (2018) by arethuza on Saturday November 23, 2019 @09:55AM (#21614397)
If you consider the actual complexity of any computer that has actually been built then a TM is, by comparison, very simple.