![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New <dne### [at] san rr com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> Darren New <dne### [at] san rr com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New <dne### [at] san rr com> 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
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |