Every program in high level (“industrial”) programming language can be expresses as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the Cartesian multiplication of the domains of all the variables and the resulting space can be the state space of the Turing machine, though the handling of computer-representable floats can be a tricky – is there such general algorithm or system that does that? https://github.com/Meyermagic/Turing-Machine-Compiler is example for the programming language for Turing machine and for the transpiler that translates C programs into the language of Turing machines or see https://web.stanford.edu/class/archive/cs/cs103/cs103.1132/lectures/19/Small19.pdf for some kind of Turing assembler language). But what about the other direction – can Turing machine be rewritten in conscise program in high level programming language that uses functions, compositionality of functions and higher-order functions?

Of course, there can be infinite results to that conversion – staring from the naming of the variables and functions and ending with the data structures, content of functions, etc. But there are metrics for the quality of the software code and maximizing such metrics can result ir more or less unique answer to this stated problem.

Such conversion is very actual in the current context of reward macines for the reinforcement learning (e.g. https://arxiv.org/pdf/1909.05912.pdf) – symbolic representation of the reward function (as opposite to tabular or deep neural represenation). Such symbolic representation greatly facilitates skill transfer among different tasks and it introduces the inference during the learning process and in such way reward machines reduces the need for data and need for learning time.

One can say that the extraction of first order and higher-order functions is quite hard tasks, but this task is being tackled by the higher order meta-interpretative learning, e.g. https://www.ijcai.org/Proceedings/13/Papers/231.pdf.

So – are there research trends, works, results, frameworks, ideas, algorithms about conversion of the Turing machine into program in high level programming language (and possibly back). I am interested into any answer – be it about the functional, logic or imperative programming.