4 ms·

It seems like I quite often see posts here about how $thing$ can perform universal computation, or simulate a UTM, or whatever. And obviously the HN readership

It seems like I quite often see posts here about how $thing$ can perform universal computation, or simulate a UTM, or whatever. And obviously the HN readership selects for these articles. But is there any significance to be found in all these things having this attribute? Does it tell us anything about the universality of computation as a property of the universe? I seem to recall that sed and C++ template installation are known to be Turing complete - and i can kind of understand that as they are designed to manipulate information, even if it is surprising that their limited syntax provides enough "power" for universality. But Tetris was not designed with this capability, yet it has it. Same with Minecraft - within which it is apparently possible to implement a Turing machine. I've seen claims that DNA replication and other naturally occuring systems may be capable of universal computation too. So in the bigger picture, whats going on here?

modarts 4y ago
A sprawling read on the topic https://www.amazon.com/G%C3%B6del-Escher-Bach-Eternal-Golden/dp/0465026567 https://www.amazon.com/G%C3%B6del-Escher-Bach-Eternal-Golden...
- andyjohnson0 4y ago
  Yep. I first read that when I was twelve. I wouldnt say I understood much back then, or even now after a number of re-readings. But its an amazing book. "Sprawling" is one word that I would use to describe it.
distcs 4y ago
> But is there any significance to be found in all these things having this attribute? Is there any significance of a beautiful painting of a magnificent sunset over mountain meadow with horses grazing?
- andyjohnson0 4y ago
  > Is there any significance of a beautiful painting of a magnificent sunset over mountain meadow with horses grazing? Yes, but it was designed that way. By a person. For other people. Its unlikely to be perceived as "beautiful" by a whale or an oak tree or whatever. But if things that weren't designed to do computation, or even designed at all, nevertheless appear to be capable of it, what does that tell us about computation? Given that the fundamental physical behaviour of the universe can (maybe) be described computationally, is computation special in some way?
  - UncleMeat 4y ago
    I don't think it needs to tell us anything about computation. It can be just a fun thing to do. We've got decades of "surprise this is Turing Complete" results. One more doesn't tell us anything about computation. But it's still fun! Think of it like writing a quine in some weird language or something. We already know it can be done. But it is still cool!
kykeonaut 4y ago
Yes, you can indeed implement a Turing machine with DNA by modifying DNA strands to simulate Wang tiles; [0] this is modeled in the abstract self assembly model. [1] You can also build emojis with DNA. [2] [0] https://thesis.library.caltech.edu/1866/1/winfree_thesis.pdf https://thesis.library.caltech.edu/1866/1/winfree_thesis.pdf [1] http://self-assembly.net/wiki/index.php?title=Abstract_Tile_Assembly_Model_(aTAM) http://self-assembly.net/wiki/index.php?title=Abstract_Tile_... [2] https://www.nature.com/articles/546687a https://www.nature.com/articles/546687a
blauditore 4y ago
Unlike the title suggests, the article/page is not a proof of Tetris' Turing completeness, but an actual implementation with UI and all. It's quite different from the other articles you're mentioning.
deleted 4y ago
[deleted]
danbruc 4y ago
I guess the main takeaway is that you do not need much in order for something to be Turing-complete. On the other hand this should hardly be surprising, all you need is something to store a state and the ability to alter the state in a few different ways depending on the current state, and of course the ability to do this over and over again. The more surprising thing should maybe be that this is all you need and that adding more features does not buy you any additional power. Then again, having some state and being able to manipulate it conditionally is a very generic building block, what else could you possibly do? So maybe it should not even be that surprising that this is all you need.
- anonymouskimmer 4y ago
  "The more surprising thing should maybe be that this is all you need and that adding more features does not buy you any additional power." The "additional power" is what questions such as P-completeness and NP-completeness is about, right? Turing-completeness, as you say, is just a very minimal set of requirements on which additional requirements are added. Otherwise we'd all just be using massively parallel arithmetic calculators as our computers.
  - danbruc 4y ago
    I am not sure that I understand your question. There are different models of computation [1] like Turing machines, finite state machines, lambda calculus or rewriting systems. A priori it could be possible that they all have different powers, that each of them is capable of solving different problems or requiring different amounts of resources like time and space to solve the same problem. But, as it turned out, this is not the case, within some polynomial factor they can all solve the same problems with the same amount of resources. Only if you add some magical feature like an oracle that provides you in constant time the answer to an NP-complete problem, you get something more powerful than a Turing machine, at least as far as we know. There you get the difference between problems in P, that can be solved in polynomial time on a Turing machine, and problems in NP, that can be solved in polynomial time with the magic device but require exponential time on a Turing machine. Quantum computers occupy a middle ground, as far as we know, they are more powerful than Turing machines but they are not magic. Using massively parallel computers is a trade-off between space and time - you need more silicon but less time, but in overall resources you are not any better off. In practice it might still matter, being able to predict the weather for tomorrow is much more useful if you can finish the calculation before tomorrow, so using more silicon and less time is a trade-off that gains you something. Also some technicalities apply, like Turing machines having an infinite amount of memory, but this does not really affect the larger picture. [1] https://en.wikipedia.org/wiki/Model_of_computation https://en.wikipedia.org/wiki/Model_of_computation
jerf 4y ago
"Does it tell us anything about the universality of computation as a property of the universe?" It tells us that computation is counter-intuitively easy to access. Our intuition says that computers are hard; look how hard they are for us to build, after all! But instead the reality is that if you try to exclude computation from a non-trivial system, it's actually fairly hard. (I think part of this intuition may also be based on our intuitive experience mostly being with von Neumann machines. Contra some other contrarians, I think we work with them for a good reason; as wild as they can be, they are much tamer than many other systems capable of universal computation. Compare with trying to work in Rule 110 directly as our primary computation method, or cellular automata in general. Many of these accidental TC systems are very strange and would be hard to work with. Getting a universal computation system nice and friendly to humans accidentally is pretty hard. Getting a universal computation system without that qualification is like falling off a bike.) https://www.gwern.net/Turing-complete https://www.gwern.net/Turing-complete is a good overview both of this concept, and includes many interesting consequences. I also particularly recommend the section title "Security Implications".
eouwt 4y ago
Imho the fact that a Turing machine is capable of universal computation is surprising/insightful. I'm not sure the fact that other simple systems are then also complete adds much more surprise/insight, even if it's difficult to predict which ones will be. What I think people often miss is the difference between computational completeness and computational "power". Yes rule 110 is complete, but what that means in practice is that you've shifted most of the work (for solving a real problem) onto specifying the initial conditions. Maybe Tetris is Turing complete but it's still a lot easier to compute 2+2 on a pocket calculator.
trynewideas 4y ago
Logic is fundamentally simple, and turning unexpected things into computational contraptions is fun.
gernb 4y ago
IIRC some people believe the universe at the smallest level just follows steps and these steps are basic and Turing complete.

modarts 4y ago

A sprawling read on the topic https://www.amazon.com/G%C3%B6del-Escher-Bach-Eternal-Golden/dp/0465026567 https://www.amazon.com/G%C3%B6del-Escher-Bach-Eternal-Golden...

andyjohnson0 4y ago
Yep. I first read that when I was twelve. I wouldnt say I understood much back then, or even now after a number of re-readings. But its an amazing book. "Sprawling" is one word that I would use to describe it.

distcs 4y ago

> But is there any significance to be found in all these things having this attribute? Is there any significance of a beautiful painting of a magnificent sunset over mountain meadow with horses grazing?

andyjohnson0 4y ago
> Is there any significance of a beautiful painting of a magnificent sunset over mountain meadow with horses grazing? Yes, but it was designed that way. By a person. For other people. Its unlikely to be perceived as "beautiful" by a whale or an oak tree or whatever. But if things that weren't designed to do computation, or even designed at all, nevertheless appear to be capable of it, what does that tell us about computation? Given that the fundamental physical behaviour of the universe can (maybe) be described computationally, is computation special in some way?
- UncleMeat 4y ago
  I don't think it needs to tell us anything about computation. It can be just a fun thing to do. We've got decades of "surprise this is Turing Complete" results. One more doesn't tell us anything about computation. But it's still fun! Think of it like writing a quine in some weird language or something. We already know it can be done. But it is still cool!

kykeonaut 4y ago

Yes, you can indeed implement a Turing machine with DNA by modifying DNA strands to simulate Wang tiles; [0] this is modeled in the abstract self assembly model. [1] You can also build emojis with DNA. [2] [0] https://thesis.library.caltech.edu/1866/1/winfree_thesis.pdf https://thesis.library.caltech.edu/1866/1/winfree_thesis.pdf [1] http://self-assembly.net/wiki/index.php?title=Abstract_Tile_Assembly_Model_(aTAM) http://self-assembly.net/wiki/index.php?title=Abstract_Tile_... [2] https://www.nature.com/articles/546687a https://www.nature.com/articles/546687a

blauditore 4y ago

Unlike the title suggests, the article/page is not a proof of Tetris' Turing completeness, but an actual implementation with UI and all. It's quite different from the other articles you're mentioning.

deleted 4y ago

[deleted]

danbruc 4y ago

I guess the main takeaway is that you do not need much in order for something to be Turing-complete. On the other hand this should hardly be surprising, all you need is something to store a state and the ability to alter the state in a few different ways depending on the current state, and of course the ability to do this over and over again. The more surprising thing should maybe be that this is all you need and that adding more features does not buy you any additional power. Then again, having some state and being able to manipulate it conditionally is a very generic building block, what else could you possibly do? So maybe it should not even be that surprising that this is all you need.

anonymouskimmer 4y ago
"The more surprising thing should maybe be that this is all you need and that adding more features does not buy you any additional power." The "additional power" is what questions such as P-completeness and NP-completeness is about, right? Turing-completeness, as you say, is just a very minimal set of requirements on which additional requirements are added. Otherwise we'd all just be using massively parallel arithmetic calculators as our computers.
- danbruc 4y ago
  I am not sure that I understand your question. There are different models of computation [1] like Turing machines, finite state machines, lambda calculus or rewriting systems. A priori it could be possible that they all have different powers, that each of them is capable of solving different problems or requiring different amounts of resources like time and space to solve the same problem. But, as it turned out, this is not the case, within some polynomial factor they can all solve the same problems with the same amount of resources. Only if you add some magical feature like an oracle that provides you in constant time the answer to an NP-complete problem, you get something more powerful than a Turing machine, at least as far as we know. There you get the difference between problems in P, that can be solved in polynomial time on a Turing machine, and problems in NP, that can be solved in polynomial time with the magic device but require exponential time on a Turing machine. Quantum computers occupy a middle ground, as far as we know, they are more powerful than Turing machines but they are not magic. Using massively parallel computers is a trade-off between space and time - you need more silicon but less time, but in overall resources you are not any better off. In practice it might still matter, being able to predict the weather for tomorrow is much more useful if you can finish the calculation before tomorrow, so using more silicon and less time is a trade-off that gains you something. Also some technicalities apply, like Turing machines having an infinite amount of memory, but this does not really affect the larger picture. [1] https://en.wikipedia.org/wiki/Model_of_computation https://en.wikipedia.org/wiki/Model_of_computation

jerf 4y ago

"Does it tell us anything about the universality of computation as a property of the universe?" It tells us that computation is counter-intuitively easy to access. Our intuition says that computers are hard; look how hard they are for us to build, after all! But instead the reality is that if you try to exclude computation from a non-trivial system, it's actually fairly hard. (I think part of this intuition may also be based on our intuitive experience mostly being with von Neumann machines. Contra some other contrarians, I think we work with them for a good reason; as wild as they can be, they are much tamer than many other systems capable of universal computation. Compare with trying to work in Rule 110 directly as our primary computation method, or cellular automata in general. Many of these accidental TC systems are very strange and would be hard to work with. Getting a universal computation system nice and friendly to humans accidentally is pretty hard. Getting a universal computation system without that qualification is like falling off a bike.) https://www.gwern.net/Turing-complete https://www.gwern.net/Turing-complete is a good overview both of this concept, and includes many interesting consequences. I also particularly recommend the section title "Security Implications".

eouwt 4y ago

Imho the fact that a Turing machine is capable of universal computation is surprising/insightful. I'm not sure the fact that other simple systems are then also complete adds much more surprise/insight, even if it's difficult to predict which ones will be. What I think people often miss is the difference between computational completeness and computational "power". Yes rule 110 is complete, but what that means in practice is that you've shifted most of the work (for solving a real problem) onto specifying the initial conditions. Maybe Tetris is Turing complete but it's still a lot easier to compute 2+2 on a pocket calculator.

trynewideas 4y ago

Logic is fundamentally simple, and turning unexpected things into computational contraptions is fun.

gernb 4y ago

IIRC some people believe the universe at the smallest level just follows steps and these steps are basic and Turing complete.