Re: On Programs That Output Themselves
- From: Chris Menzel <cmenzel@xxxxxxxxxxxxxxxxxxxx>
- Date: 6 May 2005 17:43:50 GMT
On 5 May 2005 08:35:47 -0700, Charlie-Boo <chvol@xxxxxxx> said:
> Chris Menzel, Charlie-Boo and Martin Shobe wrote:
>
>> >> Your proof applies only to those programing languages
>> >> that satisfy your axioms. In order to apply your proof to all
>> >> programming languages (which is what you claimed you were attempting
>> >> to do), you would have to show that all programming langauges satisfy
>> >> those axioms. Which means you need to have some definition of a
>> >> programming language.
>>
>> > A programming language is a mapping from a recursively enumerable
> set onto the set of recursive functions.
>>
>> Any r.e. set? If not, which? This isn't much of a definition.
>
> Yes, any. What's wrong with it?
Well, I do get a math geek charge out of abstract, general definitions,
so maybe it's just because IANACS, but I'm having trouble seeing how it
is adequate. I take it that, in your definition, the domain for a
language L represents (an encoding of?) the "programs" of L and that
L(p) is the recursive function that p "computes". This raises at least
a couple of questions. For instance, I would think that the definition
of a *language* would involve some notion of grammar (a very abstract
one, at least), yet that appears to be explicitly eschewed here.
Moreover, if the domain of a PL for you represents its programs, then,
since the domain can be RE, it seems to follow that there may not be an
effective way to tell in general whether anything is in fact a program.
That seems to be a very odd property for a programming language to have
as well, as a typical PL is presented, e.g., via a BNF grammar that
provides an effective procedure for distinguishing programs from
non-programs. Finally, a point I made previously, it seems to me that
you beg some important questions by building Turing completeness into
the definition, as there are many special purpose LANGUAGES that are
used to PROGRAM computers, and hence seem to deserve the title
"programming language".
So what it looks like to me is that your definition is not really a
*definition*, but a high level, structural *description* of the class of
(Turing complete) programming languages, viz, functions from (codings
of) programs onto the recursive functions. Granted, that may be quite
adequate for some contexts, and *maybe* it's even adequate in *this*
context, but it seems to me that it has led to more confusion than
clarity here. Notably, most of your interlocutors seem to have a more
concrete notion of a PL in mind, which suggests you have been talking
past each other rather than actually communicating.
>> > (Because of cardinality, you can't map an aleph-0 set onto an
>> > aleph-1 set.
>>
>> Why do you think this is a relevant qualification in this context?
>
> I'm just making the point that the range is a proper subset of the
> aleph-1 set.
So you were just noting that the set of recursive functions is a proper
subset of the set of all functions from N to N. Ok, but I still don't
see how that was relevant.
>> Please be specific. (And why do you seem to be assuming the
>> continuum hypothesis?)
>
> Maybe you're talking about terminology.
No, there is a substantive point here.
> I call N aleph-0 and R aleph-1. (Dumb me if that assumes CH.)
It does. (And I assume you mean that you call the *cardinality* of R
aleph-1).
> A map from a set to its powerset, ok?
Ok.
Chris Menzel
.
- References:
- Re: On Programs That Output Themselves
- From: Charlie-Boo
- Re: On Programs That Output Themselves
- Prev by Date: Re: A little knowledge is a dangerous thing - THE HALTING PROOF
- Next by Date: Re: BEHOLD....... PROOF THAT *CARDINALITY IS BONKERS*
- Previous by thread: Re: On Programs That Output Themselves
- Next by thread: Re: On Programs That Output Themselves
- Index(es):
Relevant Pages
|
