Take a Turing machine, with a terminating program, convert it to some representation of the machine which captures, in a lossless manner, its state as it performs the computation.

So you have a complete representation of the machine, the program, and its internal organisation as it performs the computation.

I am going to suggest a graphical form, nodes and edges, names for nodes.

Take a second Turing machine with a slightly different program. This program is identical save that it performs a single unit of function from the first program in a non optimal way, say it performs the single unit 3 times, changing some value to the correct output the first time, taking it to some second result the second time and then finally returning again to the correct first result. Like a reflection.

Would it not be possible for some statistical technique to analyse the graph of the two machines including their process and find a compression of the graph of the second machine, which is smaller in terms of the size of the graph of its process and yet consistent with the mode of operation of the machine.

For instance a graph matching algorithm could find that there is a subgraph match between one portion of the the process graph of the first machine and one part of the process graph of the second machine and replace the subgraph of the second machine with the subgraph of the process of the first machine.

How it would then alter the program of the second machine to generate that altered graph I am unsure of.

Do such techniques exist? Where would I find them, or is the analysis flawed or incomplete in some way which prevents its operation? What should I learn to understand its implementation or the truth of its deficiency?

  • 5
    $\begingroup$ Look at optimizing compilers. There are all sorts of such techniques, although I don't believe any of them work for the most general case. $\endgroup$ – Peter Shor Nov 2 '12 at 14:31
  • $\begingroup$ Thanks Peter, is there any theory for the general case that you know of? It's the classic "you don't know what you don't know problem", I can't find a way into the correct area of research to start getting my head around this cluster of problems... ho hum $\endgroup$ – Marcus Nov 5 '12 at 12:25
  • $\begingroup$ I don't know anything about the theory of optimizing compilers, beyond having gone to a few talks about it. I'm the wrong person to ask. $\endgroup$ – Peter Shor Nov 5 '12 at 12:33
  • $\begingroup$ I suggest to call the graphical form a trace. When you consider the relationship between the trace and the program to you allow for multiple inputs to the same program leading to potentially different traces? $\endgroup$ – Dmitri Chubarov Nov 8 '12 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.