4 ms·
> you know, Turing completeness doesn't mean you can actually port arbitrary Turing complete code on another Turing complete environment. You can't transpile x8
by greiskul 3y ago
> you know, Turing completeness doesn't mean you can actually port arbitrary Turing complete code on another Turing complete environment. You can't transpile x86_64 Linux Kernel image into a bare HTML+CSS file, or random generated and filtered valid sequence of Turing machine tape instructions into a well structured and annotated Rust code.
It depends on how you define things, but in a very reasonable definition it does actually mean that. If we consider a computational model to be a way using a finite string in countable alphabet to represent every single computable function, then yes, there is an algorithm that can take a program in any computational model 1 and find another program in computational model 2 that also implements the same computable function. Implements here means that both programs will for the same input return the same output if they both halt, or both will not halt.
Now the running time, or algorithmic complexity of both algorithms, is not under consideration here. The x86_64 program running in native hardware might finish the computation in milliseconds, where a browser that does the same computation using purely HTML and css that our universal transpiler generated might run in trillions of years.