Tag Archives: complexity

Improve chemical computing complexity by a 1000 times factor, easily

That is, if autonomous computing molecules are possible, as described in the model shown in the Molecular computers.

To be exactly sure about about the factor, I need to know the answer for the following question:

What is the most complex chemical computation done without external intervention, from the moment when the (solution, DNA molecule, whatnot) is prepared, up to the moment when the result is measured?

Attention, I know that there are several Turing complete chemical models of computations, but they all involve some manipulations (heating a solution, splitting one in two, adding something, etc).

I believe, but I may be wrong, depending on the answer to this question, that the said complexity is not bigger than a handful of boolean gates, or perhaps some simple Turing Machines, or a simple CA.

If I am right, then compare with my pet example: the Ackermann function. How many instructions a TM, or a CA, or how big a circuit has to be to do this? 1000 times is a clement estimate. This can be done in my proposal easily.

So, instead of trying to convince you that my model is interesting because is related with lmbda calculus, maybe I can make you more interested if I tell you that for the same material input, the computational output is way bigger than in the best model you have.

Thank you for answering to the question, and possibly for showing me wrong.

___________________________