Recent Posts

The Currin-Korovin DNA-based non deterministic universal Turing machine

The recent paper by Currin-Korovin et al. introduces a new physical implementation of a computer that can leverage a gigantic amount of parallelism at a fraction of the energy cost using the string rewriting model of computation and a set of clever PCR reactions. Moreover, it refers to non determinism — arguably one of the most interesting concepts in computer science — in its very title. Exciting!

Turing machine & universality

The paper introduces an interesting physical implementation of a universal Turing machine. Let me briefly explain what that means, in lay terms.

A Turing machine is an abstract (i.e., mathematical) device defined to capture the essential idea of computation. Having an abstract model allows us to look at the core mathematics of a concept rather than be bogged down by concrete physical details (power, clock rate, details of addressing memory, a specific algorithm or programming language, etc.). It’s the equivalent of the “spherical cow” of physics: it allows for a much cleaner asking and analysis of questions related to computation. A Turing machine comprises a set of rules that are of the form:

If you read symbol x and machine is in state y, then machine does z;

where z could be the act of writing a symbol, moving the cursor to a new location, or changing machine state. This set of rules — if you see a symbol in a state, what you should do — is finite and fixed, like a rule book or a medical manual. The advantage is that the machine’s behavior in any state is robot-like predictable, and therefore facilitates design and analysis. But, it restricts the machine to the one specific computational task that it was designed for: the rules for multiplication of integers are going to be different from those for counting vowels in a word.

Read Bhatia's full blog post here.

  • White Twitter Icon
  • github-icon
  • White YouTube Icon

© 2020 Living Computing Project.

Sponsored by National Science Foundation’s Expeditions in Computing Program

(Awards #1522074 / 1521925 / 1521759).