On Wed, Apr 17, 2013 at 5:33 PM, Ian Kelly <ian.g.ke...@gmail.com> wrote:
> On Wed, Apr 17, 2013 at 5:40 PM, Mark Janssen <dreamingforw...@gmail.com>
> wrote:
>> Rercursion the "bedrock" of language-design. I don't think so. From
>> what I know, a well-defined language ends at its symbols. It makes no
>> use of "infinities".
>
> From what I know, you can't have a Turing-complete language without
> some form of recursion. So yeah, it's pretty damn important in
> language design.
A Turing-complete language generally has items that are defined in
terms of other, simpler items, but this is not called recursion in any
C.S. paper I know.
In C.S. of my world, recursion is a specific term that is related to
functional calculii. This type of recursion is sometimes often found
in imperative/iterative languages, but is rooted in the fomer.
>> Conflating a programming
>> language ("an infinite object such as python language") with a program
>> written in that language ("there are an infinite number of python
>> programs"). These two are entirely separate (at least anything
>> implemented on a real computer).
>
> Mathematically, a language (e.g. a programming language) is a set of
> well-formed strings (i.e. programs) constructed from the symbols of an
> alphabet (i.e. tokens).
Mathematically, perhaps, but from C.S. theory, a language is a
fully-specified set of expressions and tokens which are considered
valid -- it's grammar.
> For most languages, this set is infinite;
This set is always finite, as you can see on the specification for
Python's language.
> saying "the Python language is infinite" is equivalent to saying
> "there are an infinite number of Python programs".
I don't think Guido would agree that "the Python language is
infinite", but then perhaps he doesn't care either.
> A finite, non-recursive grammar can only hope to accept a finite
> number of strings.
Is the language we're speaking in now one with a finite, non-recursive grammar?
--
MarkJ
Tacoma, Washington
--
http://mail.python.org/mailman/listinfo/python-list
