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.

  • 1
    $\begingroup$ We know that a compiler maps high level language to low level language. You are kind of asking how to map low level language to a high level language. To be honest I am not an expert. But here are my Observations (1) The mapping between LLL and HLL isn't 1-to-1. (2) HLL implements tools for programmer's convenience, like opcode mnemonics, identifiers, easier control-flow, etc. (3)Decompilers can find a mapping between a program written in assembly language to a equivalent program in HLL like C. $\endgroup$ – rsonx Dec 9 '19 at 9:37

https://www.longdom.org/articles/reverse-engineering-turing-machines-and-insights-into-the-collatz-conjecture.pdf is one initial effort to do this for some subclass of Turing machines. Actually there is fantastic culture about it http://bluesky-home.co.uk/. These works almost exclusively cite the author itself, that indicates how undeveloped this field is. Nonetheless, the quality of that research is at the level of peer-reviewed research and the main results are published.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.