Abstract abstracting machines

Its summary of the keynote: “Winning the War on Error: Solving the Halting Problem and Curing Cancer”.

What can you learn?

This talk can inspire you to learn more computer science. You can use programming knowledge to solve changes in curing cancer. The presenter showed how well-known problem like halt problem could inspire to solve some issues in IT world and also solve detection of a wrong genome.

Halt problem

The halting problem is a problem which tries to answer the question: is possible to say when or if executing program has ended? Alan Turing said about it:

Thou shalt not write an algorithm which determines whether a program halts

We can’t solve this problem at all, but we can approximate some solutions and give an answer in some cases. For all unknow cases we can just say “don’t know”. To provide some partial answer, we will abstract abstracting machines.

Software engineer and predictions

The real engineer should use predictions for his design. Do we do such stuff? Matt complained about it.

He showed how he used predictions to approximate programs. He needed to find malware software for the custom Android marketplace which was installed on soldiers devices. He suggested measuring the state of a program (using static analysis) and tried to answer (partially) the halting problem with an approximation. So he suggested to write it down like:

f(program)={halt problem}
f^(program)={halt problem; dunno}

The main idea is to pass program to the Interpreter then to AAM (abstract abstracting machine) and then to Approximator (Static analysers allow programmers to bound and predict the behaviour of software without ever running it.).

What’s needed to create AAM:

  • Injection function = transform program to some state
  • Step function = change state to new state
  • Approximation of execution (guarantee to stop at some point)
  • The abstracted state corresponds to some real state

He described the state of each program using CESK (Control Environment Store Kontinuation).

The CESK machine is a state-machine in which each state has four components: a (C)ontrol component, an (E)nvironment, a (S)tore and a (K)ontinuation. One might imagine these respectively as the instruction pointer, the local variables, the heap and the stack.

Writing these things to more mathematics it will be something like this:


In bold I wrote things which he needed to approximate to achieve bounded context. After all, this transformation, it is possible to determine and predict: is program well behaving.

Genome analogy to abstracting abstract machines

What is cancer? Cancer is many rare diseases. Finding the same two cancers is hard. The problem which we need to face is curing rare diseases.

Matt found the analogy of software program to biology program:

  • DNA is a collection of characters (char*) which  can accept 4 characters `A` `T“C` `G`
  • DNA is encoding RNA
  • RNA is encoding proteins
  • many proteins are enzymes (Enzymes are functions which catalyse transformation)

From that, we conclude that genome has

  • syntax
  • semantics

So we can use this analogy to build AAM and detect which part of genome fails and mutate in wrong way. Matt Might has invented some algorithm to counteract some mutations.

Real life

He used described a method to find his son disease. He discovered that his son suffers from NGLY1 mutation. What was interesting the medicament which reverts was easy to buy. He tried the medicament on himself and after that, he gave it to his son and he cured him.

In that time, President Obama would like to create the precision medicine program. And he invited Matt to build a genetic telescope and try to build customise drug to diseases. They made assumptions to try cure 5 genetic diseases in 12 months, and they managed to do it. Currently, after changes in US Matt started to create a private clinic and he will develop his project.


One thought on “Abstract abstracting machines

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s