Hacker News Reader

Comment by danbruc | Hacker News Reader

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.

View on HN

Hey Danbruc,

Interestingly, DNA computation can behave like a non-deterministic Turing machine. [0] However, as you mention, there is a clear trade-off between resources and time complexity. In this instance, the amount of DNA needed to solve an NP-Complete problem with a large input, e.g. n = 256, would require more atoms than there are in the observable universe given that the amount of DNA needed grows at a rate of 2^n.

[0] https://www.sciencedirect.com/science/article/pii/S030439750...

Any Turing machine can superficially behave like a non-deterministic Turing machine, you just have to bite the bullet and brute force the solution in exponential time or use an exponential amount of processing units. But this exactly what separates the two types of machines, requiring or not requiring an exponential amount of resources. So when I said they can be superficially similar, that actually means they are not similar, as the one thing we ignore - the required resources - is exactly the one thing that separates them.

So I think saying DNA computation can behave like a non-deterministic Turing machine is only true in the same sense that a deterministic Turing machine can behave like a non-deterministic Turing machine, i.e. not very true. The difference is the trad-off - exponentially slower vs exponentially more processing units - and there might be some use for this if you have, for some n, enough room for exponentially many DNA molecules but not enough time to wait for exponentially many clock cycles.

The primary advantage of a DNA computer might be that you can make use of all three dimensions while processors are mostly limited to two dimensions. I did not read the paper you linked to, but the DNA computations I have seen where all very slow processes, so at least in those cases I have seen, the DNA computation has to make good for many orders of magnitude of processing speed in terms of parallelism before there is even the possibility of an advantage.

"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.

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

You know far more than I do. From what little I understand the specialness of a Turing machine is that it can be used as a universal calculator, not that it can be used as a universal calculator fast.

I guess the point I was trying to make is that even if CPUs only use a Turing-complete set of gates on the fine scale, the way they are arranged and connected (for things like massively parallel operations) is what sets a modern CPU apart from a basic Turing machine. Allowing it more computational speed than an equivalent number of parallel basic Turing machines.

From what little I understand the specialness of a Turing machine is that it can be used as a universal calculator, not that it can be used as a universal calculator fast.

This depends on how you want to understand fast. A Turing machine updates only a few bits per cycle while a modern computer easily updates many thousands if not millions of bits per cycle. Also a Turing machine access its memory very slowly because the head moves one cell per cycle, good luck reading a bit stored five gigabytes away from the current position of the head. So yes, in that sense a Turing machine is slow, especially random access memory is big advantage in practice, but in theoretic terms having to scan through the entire memory just gets swept under the rug of polynomial factors.

On the other hand you can build a Turing machine that emulates your modern computer even though it might need a trillion cycles to emulate just a single cycle of it. But mathematically you can just factor this out, you call a trillion cycles just one cycle and now both are the same speed, mathematically of course, not any physical implementation.

The other way that you allude to, using many Turing machines in parallel, is probably more realistic. You can probably build a small Turing machine with the equivalent of a few hundred or maybe few thousand gates. And you can program them to simulate a single logic gate in maybe ten or so cycles. Now rebuild you real computer with all gates replaced by those small Turing machines.

My gut feeling is that you could probably build a 80s or 90s era processor using current technology. A 1982 Intel 80286 has 134,000 transistors, that puts the number of gates well below 100,000 while a GeForce RTX 4090 has 16,384 shader cores which are way more powerful than our tiny Turing machine to simulate a single logic gate needs to be. So if you are willing to give up 30 years of Moore's law, you can probably have a Turing machine powered computer.

Heck [2], we have transistor level simulations of old processors [1], somebody with enough enthusiasm could probably do this at the gate level, then replacing gates with Turing machine simulations would be easy, and finally you would have to get them running on a GPU for decent speed, but I am not sure if GPUs would be any good for that kind of task, I have never programmed one. But this would be a processor running some code, simulated at the gate level with the gates implemented by Turing machines simulated on a real processor.

[1] http://visual6502.org/JSSim/index.html

[2] Is there any good replacement for heck, I think it has a negative connotation? But maybe stronger than look.

When used as an intensifier heck, hell, and equivalents are fine. They lose the negative connotation as intensifiers. At least IMO.

The only difference between a Turing machine and a finite state machine is that the Turing machine has a writeable tape with a movable head.

There is not much to it.

I think the deciding factor is that you can compose individual operations into new operations and use any previous result as input into the next computation.

Reply on news.ycombinator.com