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)
>>1
OP look up formal grammar and automata theory. Both of them have parallels. For example a turing machine can be described using a corresponding formal language a "type 0" language IIRC. A finite state machine can be described using a "regular language etc.
Name:
Anonymous2012-11-12 5:49
So basically we have an approximation to a Turing machine, which is any sort of processor with memory, upon which we build upon the physical grammar of the structure of the system a grammar of machine code upon which we build consequential layers of abstraction resulting in a "language" which would take as input the arbitrary physical abstractisized grammars of arbitrary input devices (kb, mice, scanners) and produce an arbitrary set of outputs using abstractisized buffers between output devices for interface.
e.g. we talk to the computer and the computer talks to us using a myriad of way - fascinating once you think about it.
Love, Liberal Arts'' production management fag
Name:
Anonymous2012-11-12 6:06
The "machines" we refer to, when we say a turing "machine" is an abstaract mathematical concept. Defined by ... You need to understand this first OP
Lisp started off as an alternative notation for the Turing Machine
Name:
Anonymous2012-11-12 11:02
OP is right.
A ``program'' is a Turing machine simulated by a universal Turing machine (the computer), and of course every Turing machine describes a language.
Name:
Anonymous2012-11-12 14:44
>>13
sorry I made a mistake in this post. It is actually accepts a language