So the definition of a compiler I got is that:

A compiler takes a string as input and checks if that string is syntactically correct, then outputs "Yes" or "No".

So does that mean all compilers are Turing Machines?

  • $\begingroup$ That’s a very strange definition. Usually compilers take code in one language and output equivalent code in another. $\endgroup$ – Yuval Filmus Jun 14 '19 at 20:58

No, a compiler takes as string as input and checks if that string is syntactically correct. If it is, it outputs another string (code in a different language, e.g., machine code) that is equivalent to the input; if it is not, it outputs "syntax error".

A Turing machine is an abstract machine (i.e., a description of a machine, rather than an actual physical thing) that performs computations. According to the Church–Turing thesis, anything that can be computed by any physical system can be computed by a Turing machine. Since compilers are implemented on physical systems, one could, in principle, design a Turing machine that computes the same mapping from strings to strings as any given compiler. But it's not true that a compiler is a Turing machine; rather, a compiler does something that a Turing machine can also do.

| cite | improve this answer | |
  • $\begingroup$ Compiler also checks that the input string is semantically correct. $\endgroup$ – gnasher729 Jun 15 '19 at 23:25

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.