 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
>> You realize that in O(1), the 1 is the *output* of the analysis, right?
> I don't understand that.
The notation puts its result in the location where most functions take their
input. O(1) has nothing to do with the size of the input being fixed.
>>> The only way for an algorithm to be O(1) is that it does *not* depend on
>>> any amount of input.
>
>> Correct. The algorithm runs the same number of steps regardless of how much
>> input you give it. That's O(1). "Return the first element in your input" is
>> an O(1) operation.
>
> How is that different from "sort the first 10 elements of the input"
> (which is basically equivalent to "sort an array of 10 elements")?
That's O(1), certainly.
>>> But O(1) is not nonsensical. It's commonly used.
>
>> It's commonly used, but not on algorithms with fixed-size inputs. If you
>> have a sort that only accepts 10 integers to sort, O() isn't defined,
>> because O() asks how fast does the algorithm run as you give it more than 10
>> inputs.
>
> Hence with your "return the first element in your input" O() isn't defined
> either.
When you said "sort 10 elements is O(1)", I interpreted you to mean that any
algorithm that takes a fixed input is O(1). There's a subtle difference
between "sort the first 10 elements" and "sort 10 elements".
If you meant "any algorithm that only looks at a fixed number of elements of
its input regardless of how many are supplied is O(1)", I'd probably agree
with that after thinking about it a while and clearly defining the term
"input". That wasn't what I was interpreting you to say. I had understood
you to be talking about algorithms whose input is by nature fixed.
For example, it's not reasonable to say "since real computers have a fixed
amount of memory, any algorithm you run on a real computer is by definition
O(1)". You said
> Any problem on a computer with limited resources is O(1).
Any problem on a computer with limited resources does not have an order
notation, since Big-O is defined only when inputs grow increasingly large
without bound. "Sort the first 2^32 elements and crash if you have more" is
not an algorithm to which Big-O notation applies, because when "n" gets to
2^33, there's no function that is below O(1) that says how long the
algorithm takes. It just isn't defined.
--
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 23-7-2009 10:30, Invisible wrote:
> 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 Planck times. What was your point?
>
> Damn, that's a nice calculation. I wish I had the data to do crap like
> that! :-D
Not that difficult. Your cellphone has presumably several megabytes of
storage. One MB corresponds to roughly 10^(2400000) states. (8million
bits 2^10N is approx 10^3N)
Number of particles in the universe, don't know, but number of atoms is
generally though to be around 10^80. Number of particles is much larger
say by a factor of 10^10 (which may be an overestimation). total so far
10^90. Age of the universe 3.5e17 seconds. Planck time 5.4e-44. so about
6e60 planck times. Multiply: 6e150 which still leaves a factor of
10^2399849 to play with.
Probably lots of math mistakes, but you get the point.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 23-7-2009 11:01, Invisible wrote:
>
> 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.
I think there are even languages that would promote the 5 to a string to
be able to do a string concatenation if you had chosen another boolean
expression that was false.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 23-7-2009 1:22, Darren New wrote:
> andrel wrote:
>> That is a rather useful definition, but it may have to imply that the
>> code that you jump to is not reachable in any other way. Or perhaps
>> that is what you want.
>
> As long as you haven't executed it before you goto it, you're OK. If you
> skip forward over something, then branch back to it, then fall into what
> you've already executed, you'll execute the same bit of code twice. But
> you can't execute it *three* times without branching to something you've
> already executed.
skip part A, do something, skip part B, do something2 then second time
jump to C and third time to D, jump to B, C: jump to A, D: continue
having executed someting2 thrice.
>> 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.
>
> It depends on the type system. Some are. Most aren't. I'm talking about
> the ones that aren't. :-)
Ah ok.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
andrel wrote:
> skip part A, do something, skip part B, do something2 then second time
> jump to C and third time to D, jump to B, C: jump to A, D: continue
> having executed someting2 thrice.
You're going to have to be a bit clearer than that for me to follow exactly
what you meant, but Ok.
Even with that, the rule would mean you can't execute any instruction more
often than you have instructions in the program, since you can only branch
to each instruction at most once. Since programs are finite, you can't get
in an infinite loop.
--
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:
> This seems relevant:
>
> http://en.wikipedia.org/wiki/Rice%27s_theorem
>
> Now, if only it wasn't completely incomprehensible...
So, to summarise:
For any property that some functions have and some functions don't
have, it is impossible to tell whether a given function has that
property just by examining the computer program that implements the
function.
(Or rather, for one specific program it might be possible, but it's not
possible for *every possible* program...)
Is that about right?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Invisible wrote:
>
>> This seems relevant:
>>
>> http://en.wikipedia.org/wiki/Rice%27s_theorem
>>
>> Now, if only it wasn't completely incomprehensible...
>
> So, to summarise:
>
> For any property that some functions have and some functions don't
> have, it is impossible to tell whether a given function has that
> property just by examining the computer program that implements the
> function.
>
> (Or rather, for one specific program it might be possible, but it's not
> possible for *every possible* program...)
>
> Is that about right?
Yes, that sounds right to within the limits of english prose vs mathematics.
:-) Pluralize "computer program" and you're a touch closer, since there can
be many programs that implement the same function, but you can't tell what
they are. ;-)
Basically, you can think of it as "you can turn any problem into the halting
problem." Anything that some programs do and some don't, you can turn into
the halting problem.
--
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> So, to summarise:
>>
>> For any property that some functions have and some functions don't
>> have, it is impossible to tell whether a given function has that
>> property just by examining the computer program that implements the
>> function.
>>
>> (Or rather, for one specific program it might be possible, but it's
>> not possible for *every possible* program...)
>>
>> Is that about right?
>
> Yes, that sounds right to within the limits of english prose vs
> mathematics. :-) Pluralize "computer program" and you're a touch closer,
> since there can be many programs that implement the same function, but
> you can't tell what they are. ;-)
>
> Basically, you can think of it as "you can turn any problem into the
> halting problem." Anything that some programs do and some don't, you
> can turn into the halting problem.
I wonder how many of these properties are decidable for "real-world"
programs... I mean, the halting problem talks about ANY POSSIBLE
PROGRAM. You could write something really freakin' bizare, and there's
no hope of an algorithm puzzling it out. But I wonder if there are any
useful properties that are decidable (or typically decidable) for useful
programs...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> the halting problem talks about ANY POSSIBLE
> PROGRAM. You could write something really freakin' bizare, and there's
> no hope of an algorithm puzzling it out.
I think the Mandelbrot set is interesting here. You can write a program
that computes how many iterations it takes for a specific orbit to
escape. The set of inputs for which this program does not halt is
precisely the Mandelbrot set - and as we all know, the boundary of this
set is ludicrously complex. You can try to parameterise it in various
ways. You can just run the iteration, you can try to make use of the
repeating geometry, but no matter which way you look at it, any possible
algorithm is going to take an infinite number of steps *somewhere* along
the boundary. It's an inescapable and obvious fact that you simply can't
determine whether *every* point is inside or outside the Mandelbrot set
in a finite number of steps.
I find that a useful way to think about the Halting Problem. It shows
that the program in question doesn't even need to be complicated...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> I wonder how many of these properties are decidable for "real-world"
> programs...
There are many useful properties which are easy to determine, yes.
That you didn't violate the type system. That you didn't use a variable
before you assigned to it. Etc. However, most of those types of properties
are restricted to the "I can prove you don't" versions, as mentioned earlier
in the type system discussion.
Depending on the implementation language, it may be feasible to prove lack
of deadlock, lack of livelock, compatibility between server and client,
compatibility between two servers (i.e., a client that works with serverV1
will also work with serverV2), and so on. However, it often gets very
exponential very quickly, especially in more procedural vs functional
languages.
--
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
|
|
| |
| |
|
|
|
|
| |
|
|
