It is known that every program or every algorithm can be converted to Turing machine. But what about the reverse process? Is there algorithm (or research trend that considers such algorithm) to convert some Turing machine into algorithm as expressed in some high level programming language (e.g. in Algol, Java, Prolog, Haskell)? The comprehensiveness/conciseness or such resulting algorithm can be defined as one having the minimal number of aggregated operations or the minimal length of the program code or the minimal number of variables or the minimal number of states (if one considers the operational semantics of the resulting program)?

I can imagine that several ways can be followed (I am not expert in any of the mentioned fields, so, theses are only musings that may have been already discovered but with such names that I can not Google them):

  • On can convert Turing machine to lambda expressions and them do some kind of term rewriting of them.
  • On can convert Turing machine to its operational semantics expressions, do transformations in the semantics domain and then extract the software code from the transformed semantics.

This question can be extended more broadly - take some low level code (e.g. lot of Prolog like rules) and extract concise algorithm from them.

The mentioned problem constantly arises int the decoding process or neural networks. There are efforts to extract set of rules from the neural networks. So - how to convert this large set of rules into concise algorithm? There are efforts to extract deterministic finite automaton from the neural network that accepts or rejects the strings that belong or don't belong to some simple language. So - why bound us with DFA? We should consider full Turing machine and try to convert it into algorithm. This problem should be solved if we are required to create explainable neural networks.

Of course, I am aware about code optimization and program analysis, but I feel that this question is far beyond that.

This question has some similarity with reverse engineering of assembler programs, maybe it can be good staring point as well?


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.