# What is the exact relation between programming languages and Turing machines?

I don't know much about yacc, bison, flex or lex and please correct me if I'm wrong but a programming language is also a Turing machine and a Turing machine is defined as the tuple $(Q, \Gamma, b, \Sigma, \delta, q_0, F)$ where $Q$, $\Gamma$, $b \in \Gamma$, $\Sigma \subseteq \Gamma \smallsetminus \{ b \}$ as input, $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{ L, R, N \}$ as transition function where $L$ = number of steps to the left, $R$ = number of steps to the right, $N$ = "standby", $q_0 \in Q$ is the initial state and $F \subseteq Q$ is the set of end states.

How similar is implementing a programming language to implementing a Turing machine? Can it be said that what is done when a programming language is implemented is that a Turing machine like the above is defined? If yes, how come we can't just use a model that looks like the definition of a Turing machine when a programming language is defined? Instead something else like BNF seems to be the standard.

• The exact relation is this: Turing Machines are a particular programming language. – Andrej Bauer Mar 7 '13 at 1:08
• BNF, Backus-Naur form can be thought of as a CFL representation system. most programming languages are CFLs. a compiler [in general] converts the input program and CFL specification to object code. (assembly language is one example of a non-CFL like language). so there might be more than one question here. – vzn Mar 8 '13 at 4:04
• @vzn: I don't know how what you say relates to the question, but it's wrong in any case. – Raphael Mar 8 '13 at 7:03
• what is wrong? repeat, most programming languages are CFLs (or have a core CFL-like parser) with various technical qualifications. – vzn Mar 8 '13 at 16:21
• What is wrong is that you think of programming languages in terms of grammars, when it is better to think of them as computational models. – Andrej Bauer Mar 9 '13 at 0:11

Maybe I'm misreading the question, but it sounds like there's some confusion in the comparison between Turing machines and programming languages.

The definition and method of defining a Turing machine constitute a programming language. Turing machines represent programs in that language.

Language syntax and semantics (e.g., in BNF) can constitute a programming language, and artifacts which satisfy those syntactic and semantic constraints are programs in that language.

So it's not really precise (IMHO; of course we can think about what TMs do in different ways, and in some of these ways of looking at TMs, you could think of individual TMs as defining programming languages. Indeed, a classically constructed universal Turing machine defines a very clear programming language, i.e., representations of Turing machines as strings) to compare implementing a programming language to implementing a Turing machine. Implementing a programming language involves defining the rules of the game, much like Turing defined the rules of the game (or whoever it was, whatever) when he defined what it meant for something to be Turing machine.

"Implementing" a programming language, and defining Turing machines, is a very difficult activity. Writing programs in a language, and defining specific Turing machines, is also a difficult activity. But they are quite different activities (except in those exceptional cases where you're writing a Turing machine to act as an interpreter, in which case maybe it makes sense to talk about designing a programming language via writing a TM... but I'm not sure this is what you were after).

The Turing machine model is a theoretical model of what "computing" is all about. As a theoretical model it was designed so it is simple to manipulate and to prove things about it, specifically to explore what can or can't be computed. It also serves as a simple model in which to discuss (and prove things about) the time required to do a computation, or how much space (memory) is required. The emphasis is on simplicity (specially in using only basic mathematical concepts).

A programming language, in contrast, is designed to make it easy to write (and read!) by humans, often also such that the concepts of its application area are handled directly. For example, a language like Perl handles operations on strings, even complex stuff like searching for patters, directly. SQL is tailored to operating on relational databases, doing queries searching for data with certain constraints and manipulating the database. And so on.

The Church-Turing thesis asserts that anything that can be computed in any meaningful sense of the term can be computed by a Turing machine. This is the final outcome of a decade-long frenzy in comming up with models of computation, all of which turned out equivalent. So, in theory, yes, they are equivalent (as far as the definition of the language and its implementation, and the machine on which it runs are correct). But as the saying goes, in theory, theory and practice are the same thing; in practice, they are very different. To write down a Turing machine to do even simple tasks is a lot of painstaking work, and that might be just one simple line in your favorite programming language.

• We have to keep in mind that real computers do things not covered by the TM model, e.g. I/O. – Raphael Mar 8 '13 at 7:10

True, all (general purpose) programming languages are believed to be equivalent to the Turing machine. (According to the Church-Turing thesis, they will not compute more, and usually it is clear how to simulate a TM in your favourite language). That does not mean that programming a Turing machine is a practical thing to do. Far from it. To do real programming better languages are developed. In fact those languages evolve over time, when we learn what features make programming languages simpler to use, or less error prone.

Still, the Turing machine is around. It serves as a yard stick to define complexity, and computability.

(added.) As noted in the comments, not every programming language is designed to be of Turing power, some deal with specific tasks, like regular expressions. On the other hand, there are powerful exotic languages disgned in such a way to make programming virtually impossible. For fun.

• @DaveClarke Indeed. That is what I intended to state, but you are right, efficiency is not complexity. I will change the word. thanks. – Hendrik Jan Mar 7 '13 at 15:21
• "True, all programming languages are believed to be equivalent to the Turing machine, see Church-Turing thesis." -- equivalence of a programming language and TMs can be (and is) proven (when true; there are less powerful languages!), and it's not the Church-Turing thesis. – Raphael Mar 8 '13 at 7:05
• Also, we have to keep in mind that real computers do things not covered by the TM model, e.g. I/O. – Raphael Mar 8 '13 at 7:10
• @Raphael. I try to rephrase the Church-Turing bit. Thanks. I agree a TM is not a real computer, but I/O (reading and writing) is one of the things you can do with a TM. – Hendrik Jan Mar 8 '13 at 11:46
• Good answer, but I too find it a bit too strong to say that all (useful, and not to exotic) programming languages are equivalent to Turing machines. I mean, vanilla SQL (without fancy add-ons) and regular expressions (not even just the theoretical kind) are two examples of useful "programming languages" that aren't Turing equivalent, but they're very useful. – Patrick87 Mar 8 '13 at 23:57

A programming language is a carefully constructed equivalent of a Universal Turing Machine.

nice question, but you're overthinking this. getting lost in the symbols. lets look at it all in a simple, basic way. a programming language is in ASCII or say just 0/1 bits for characters. now imagine the TM has 0/1 bits to simplify it, or say ASCII as input characters.

the key realization, and analogy, is that TM state table doubles as reading the input character set, and containing the programming language/program encoding.

this can be realized by building or examining simple TMs & their state tables to compute basic calculations eg sums or whatever. another very useful approach is to play with TM simulators.[3]

all this would be much more obvious if in some classes they taught CS using real TM compilers that would take an arbitrary program (source code) and compile it into a TM state table (similar to object code). unfortunately, nobody believes that is useful right now.[1] (plz vote to reopen if you disagree! =)

but if you play with TM simulators, it will help you build this basic intuition. [2] is possibly the most sophisticated available in the world right now.

[2] TM compiler in ruby with example source/object code & output (for a nonhalting $a+b=b+a$ commutative addition law verifier)

• The comment about your other question is not only unnecessary, but also wrong (and assuming). – Raphael Mar 8 '13 at 7:08