This question is the generalization of my question on ComputerScience.SE: How to translate automaton (Turing machine) into the program of high level programming language?
Turing machine can be considered as special, algorithmically represented function that maps binary string on the input to the binary string in the output. Essentially, Turing machine is defined by the tabular rules. My question is
Can such function be reexpressed using more traditional and conscise functions and constructions - be it imperative, functional or logic program?
Software quality metrics for the source code can provide guidance. Does mathematics have some branch to express low level function with high level, compisitional and even higher order (that takes as arguments other functions not just their return values) functions?
Of course, I know about Fouries series, about Kolmogorov-Arnold theorem, but they don't apply there, because they are somehow noncompositional and to uniform and even with infinities.
Have mathematicians seen or thought about such issues, maybe in other contexts?
Reformulating your question, you look for a general approach for a Turing-complete languages to "extract" knowledge from a low-level data. Having similar questions on the concept of emergence in mathematics, I stumbled upon a number of things that may be relevant to you. In logic: representability, definability, expressivity, particularly Beth-definability theorem, of course Godel's incompleteness theorem may be relevant (and, more generally, hierarchy of arithmetical definability). In software verification (my field): invariants and invariant representations (one article of particular interest is Padon, O., Immerman, N., Shoham, S., Karbyshev, A., & Sagiv, M. (2016). Decidability of inferring inductive invariants. ACM SIGPLAN Notices, 51(1), 217-231.), synchronization/relational invariants and program equivalence/program products (see, e.g. Mordvinov, D., & Fedyukovich, G. (2019). Property Directed Inference of Relational Invariants. 2019 Formal Methods in Computer Aided Design (FMCAD), 152-160.).