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

Problem Detail: 

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.

Asked By : Dac Saunders

Answered By : Patrick87

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10338