andrel wrote:

> Aside: Your cell 
> phone's state space far exceeds the number of particles in the universe 
> multiplied by the age of the universe measured in Plack times. What was 
> your point?

Damn, that's a nice calculation. I wish I had the data to do crap like 
that! :-D

Post a reply to this message

>> Nah. It's useful to know you haven't violated the type system, and 
>> that's decidable.
>
> I seem to remember that type systems had the same complexity as or might 
> even be Turing machines in themselves, but I assume you know better.

The way I heard it, it is undecidable whether an arbitrary program is 
"type-safe". (I.e., it never tries to perform an operation on an 
unsuitable type.) So various type systems have been invented where it is 
decidable whether a given program is "well-typed" (i.e., it fits the 
rules of the type system). Under this definition, certain programs which 
are type-safe are rejected as ill-typed because they violate some 
restriction of the type system.

In other words, the type system is an artiface invented to turn an 
undecidable problem into a decidable one.

For example:

   5 + (if 1 == 1 then 0 else "yellow")

This is type-safe (it produces the answer 5), but most type systems 
would reject this as ill-typed.

Of course, by the time you get to Haskell with a few language extensions 
turned on, the automatic type inferrence engine is basically a Prolog 
program that gets run at compile-time, and can take an unbounded amount 
of time (and space) to terminate...

Post a reply to this message

>> Now, if only it wasn't completely incomprehensible...
> 
> What part do you not understand?

OK, so let me get this straight:

If there exists a property that some programs have and some other 
programs do not have, it is impossible to tell which programs have this 
property.

This seems downright false. For example, some programs contain a 
variable named "X", while others do not. Yet it is trivial to determine, 
for any possible program, whether or not it contains such a variable. So 
this cannot possibly be what Rice's theorum is saying.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> So if your input isn't unbounded, then O() doesn't make much sense.

  Of course it makes sense. "How many steps are needed to sort an array
of 10 elements?"

  You are basically arguing that "O(1)" doesn't make sense.

-- 
                                                          - Warp

Post a reply to this message

Invisible wrote:
>>> Now, if only it wasn't completely incomprehensible...
> If there exists a property that some programs have and some other 
> programs do not have, it is impossible to tell which programs have this 
> property.
> 
> This seems downright false. For example, some programs contain a 
> variable named "X", while others do not. Yet it is trivial to determine, 
> for any possible program, whether or not it contains such a variable. So 
> this cannot possibly be what Rice's theorum is saying.

As noted in the first sentence of the Wikipedia article:

"Rice's theorem states that, for any non-trivial property of partial 
functions, there is no general and effective method to decide whether an 
algorithm computes a partial function with that property."

Wheather or not a program contains a variable named "X" is not a 
property of the function which it's computing -- it's only a property of 
the program itself so Rice's theorem doesn't apply.  Also note that 
generally within this context the functions are assumed to be on the 
natural numbers.

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> So if your input isn't unbounded, then O() doesn't make much sense.
> 
>   Of course it makes sense. "How many steps are needed to sort an array
> of 10 elements?"

But O() notation is defined as a function related to an "n" input size that 
grows without bound.

"""
In mathematics, computer science, and related fields, big O notation 
describes the limiting behavior of a function when the argument tends 
towards a particular value or infinity, usually in terms of simpler functions.
"""

http://en.wikipedia.org/wiki/Order_notation

What's the argument that's tending towards infinity?

>   You are basically arguing that "O(1)" doesn't make sense.

No, it makes perfect sense as long as some input value is getting 
progressively larger. (Or heading towards a value that takes progressively 
more time or space.)  O(1) is the *output* when the *input* grows without 
bound. If your input grows without bound, the function isn't meaningful.

-- 
   Darren New, San Diego CA, USA (PST)
   "We'd like you to back-port all the changes in 2.0
    back to version 1.0."
   "We've done that already. We call it 2.0."

Post a reply to this message

Invisible wrote:
> The way I heard it, 

That's my understanding too.

> In other words, the type system is an artiface invented to turn an 
> undecidable problem into a decidable one.

... which is why it so often tickles me to see people complaining about a 
language that (for example) won't let you use conditionally-uninitialized 
variables, without complaining about it preventing things like ...

>   5 + (if 1 == 1 then 0 else "yellow")


-- 
   Darren New, San Diego CA, USA (PST)
   "We'd like you to back-port all the changes in 2.0
    back to version 1.0."
   "We've done that already. We call it 2.0."

Post a reply to this message

Invisible wrote:
>>> Now, if only it wasn't completely incomprehensible...
>>
>> What part do you not understand?
> 
> OK, so let me get this straight:
> 
> If there exists a property that some programs have and some other 
> programs do not have, it is impossible to tell which programs have this 
> property.

Almost. The "property" is a property of the language the program accepts, 
not the program. Note that a "language" in this case isn't the programming 
language, but the mapping from inputs to outputs. In other words, a 
"property" is a relationship between input and output, not a property of the 
text of the program.

A "property" of a program is the subset of all possible functions that has 
that property.  The property "halts when given an empty string" is defined 
as "the set of all programs that halt when given an empty string." The 
property "outputs the word 'green' somewhere" means "the set of all programs 
that output the word 'green' somewhere".

The theorem states that you can't tell what properties a function has. In 
other words, if you look at a property as a collection of functions that 
does *that*, then you can only tell if a function has it or not only if that 
set is universal or empty.

Spend a couple minutes looking at the "formal statement".

> This seems downright false. For example, some programs contain a 
> variable named "X", while others do not. 

That's not a property of the program. That's a property of the source code 
used to describe the program. The exact same program may or may not have an 
X. If you replace X with Y everywhere, the exact same program (defined in 
terms of its inputs and outputs) doesn't have an X.

-- 
   Darren New, San Diego CA, USA (PST)
   "We'd like you to back-port all the changes in 2.0
    back to version 1.0."
   "We've done that already. We call it 2.0."

Post a reply to this message

Kevin Wampler wrote:
> generally within this context the functions are assumed to be on the 
> natural numbers.

Or, more precisely, someone has already proven that any possible input and 
output can be mapped isomorphically into the natural numbers.

-- 
   Darren New, San Diego CA, USA (PST)
   "We'd like you to back-port all the changes in 2.0
    back to version 1.0."
   "We've done that already. We call it 2.0."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> No, it makes perfect sense as long as some input value is getting 
> progressively larger. (Or heading towards a value that takes progressively 
> more time or space.)  O(1) is the *output* when the *input* grows without 
> bound. If your input grows without bound, the function isn't meaningful.

  I didn't understand that.

-- 
                                                          - Warp

Post a reply to this message