2
$\begingroup$

Every program in high level ("industrial") programming language can be expressed 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 tricky - is there such general algorithm or system that does that? https://github.com/Meyermagic/Turing-Machine-Compiler is an 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 concise 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 - starting 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 in more or less unique answer to this stated problem.

Such conversion is very actual in the current context of reward machines 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 representation). 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 reduce the need for data and need for learning time.

One can say that the extraction of first order and higher-order functions is a quite hard task, but this task is being tackled by the higher order meta-interpretive 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.

Improve this question
$\endgroup$
5
  • 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, 2019 at 9:37
  • 1
    $\begingroup$ Hi. Why are you interested in doing this particularly for Turing machines? There are other definitions of computation which are more convenient as programming languages, for example, lambda calculus. I do not understand the connection between reinforcement learning and Turing machines. Can you elaborate on that? $\endgroup$
    – beroal
    Feb 27, 2020 at 15:21
  • $\begingroup$ Connection between RL and TM: Universal AI AIXI model (by Marcus Hutter, currently at DeepMind) formulates general string prediction problem - how to predict next string (action/reward) from the history of the past observations/actions. RL is specific solution to this general problem, which learns the unknown environment and learns to live in/act on it optimally. There are lot of work about deep RL that learns Value and Reward functions (from which the next action or policy generally can be deducted) and there are some works that extracts Turing machine from the neural networks. $\endgroup$
    – TomR
    Feb 27, 2020 at 15:35
  • $\begingroup$ ... so - my idea was: extract TM from the Value and Reward functions and then convert TM in conscise format, e.g. in high level program. In such a way we go from the black-box deep RL (which is bad in the age which requires explainable AI) to the RL as inference. Why TM? Why convert NNs into TM and not into lambda terms? Actually direct conversion should be possible, but it is quite easier to get TM from NNs, because it requires just to extract state space and transitions among states and this can be done by the usual methods of clustering, no new ides. $\endgroup$
    – TomR
    Feb 27, 2020 at 15:38
  • $\begingroup$ Well, if there could be ideas how to extract directly lambda functions directly from the NN as functions, then it would be great to do just that. Such extraction requires search over large space of lambada functions. I can imagine that Evolutionary Programming (which allows genes to encode the grammatically correct expressions only) is solution and it is been applied to program induction, but I fell that the longer path: V/R functions as NNs -> TMs -> high level program is more pragmatic path, that explicitly handle the symbolic search and recovers the NNs in more exact way. $\endgroup$
    – TomR
    Feb 27, 2020 at 15:42

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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