Name: Anonymous 2012-11-11 19:47
Any CSfag here? I'm wondering about something.
As you know, a computation can be defined as an automaton recognizing a string. So (as I infered from what I learned back then) a program can be formally defined as an automaton.
But then again we also know that an automaton also defines a grammar, thus defines a language (e.g a programming language's syntax is defined by a pushdown automaton). Does that make a program equivalent to a language? (It actually makes sense, aren't compilers and interpreter and whatnot realization of their language? a ``normal'' program then can be viewed as a non-Turing complete language recognize whatever input as its program)
But then again a computer is a realization of a Turing Machine, which is a kind of automaton (a very powerful one at that).
Does that make program, language and computer all equivalent?
(And if I replaced automaton and Turing machine with the equivalent lambda calculus, how do I formally define computation? Just use functions in place of state and reduction/evaluation instead of transition right? Sorry if I'm asking something stupid, I only know about lambda calculus through functional programming so I'm not sure how it's used in theory of computation)
As you know, a computation can be defined as an automaton recognizing a string. So (as I infered from what I learned back then) a program can be formally defined as an automaton.
But then again we also know that an automaton also defines a grammar, thus defines a language (e.g a programming language's syntax is defined by a pushdown automaton). Does that make a program equivalent to a language? (It actually makes sense, aren't compilers and interpreter and whatnot realization of their language? a ``normal'' program then can be viewed as a non-Turing complete language recognize whatever input as its program)
But then again a computer is a realization of a Turing Machine, which is a kind of automaton (a very powerful one at that).
Does that make program, language and computer all equivalent?
(And if I replaced automaton and Turing machine with the equivalent lambda calculus, how do I formally define computation? Just use functions in place of state and reduction/evaluation instead of transition right? Sorry if I'm asking something stupid, I only know about lambda calculus through functional programming so I'm not sure how it's used in theory of computation)