is it possible to build a turing machine that programs a given API?
-
26-06-2021 - |
Question
I was wondering, is it possible to define an API and give it as an input to a TM
turing machine and the output will be the code in c
or any other natural/programming language?
I guess not but how do I show it formally by reduction etc. ?
Solution
Your question seems to be asking if it is possible to write a program (in other words, a Turing Machine) that takes in a program specification (what you are calling an "API") and outputs a program in some programming language. The answer to this is "of course". Let's look at a few examples.
Let's say I write my input specification as a C program and I want to output a program in C. I call this Turing Machine program "copy" and I can trivially implement it in any language (or use the
cp
command on the command line).Let's say I write my input specification as a C program, and I want to output a program in assembly code. I call this Turing Machine program "compiler" and I can implement it in any language (or you can download a C compiler that already exists).
Let's say I write my input specification in English and I want to output a program in C. I call this Turing Machine program "software engineer" and I implement it in the brain of a human by sending that human to school (or you can hire an existing software engineer).
The moral here is that a Turing Machine can do anything that a human can do (and a human can do anything a Turing Machine can do). But it's really, really, really hard to write a computer program that is as general-purpose as a human.