OK, so Darren will know the answer to this one...

It's common knowledge that if you write an arbitrary program in a 
Turing-complete programming language, it is impossible to determine 
whether the program will ever halt.

This poses several interesting questions. For example:

- What is the "most powerful" language for which you *can* tell is an 
arbitrary program will halt?

- If you have an arbitrary program written in a Turing-complete 
language, which properties *can* you determine, and which ones *can't* 
you determine?

You can't determine whether the program halts after a finite or infinite 
number of steps. But you can trivially determine whether it halts after 
less than 1,000 steps. You can't determine if it's type-safe [only 
whether it is well-typed according to some more restrictive set of 
rules]. Can you determine whether a particular execution path is ever 
taken? Or whether a given variable will ever be read/written? You can't 
determine whether two programs do the same thing, but can you determine 
whether one algorithm is the inverse of another? And so on...

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> It's common knowledge that if you write an arbitrary program in a 
> Turing-complete programming language, it is impossible to determine 
> whether the program will ever halt.

  That's not stated correctly. It's impossible to create an algorithm which
would tell for all possible programs whether they terminate or not.

  It is, rather obviously, possible to create an algorithm which tells for
*some* programs whether they terminate or not.

  In other words, in the generic case the problem is unsolvable, but in
specific cases it can be solved.

> Can you determine whether a particular execution path is ever 
> taken? Or whether a given variable will ever be read/written?

  That's completely (and rather trivially) equivalent to the halting problem.

-- 
                                                          - Warp

Post a reply to this message

>> It's common knowledge that if you write an arbitrary program in a 
>> Turing-complete programming language, it is impossible to determine 
>> whether the program will ever halt.
> 
>   That's not stated correctly. It's impossible to create an algorithm which
> would tell for all possible programs whether they terminate or not.

Right. You can't solve the problem for all possible programs, only for 
some of them.

So what's the smallest limitation you could impose on the programs to 
make it possible to solve them all?

>> Can you determine whether a particular execution path is ever 
>> taken? Or whether a given variable will ever be read/written?
> 
>   That's completely (and rather trivially) equivalent to the halting problem.

I had a sinking feeling it might be...

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> So what's the smallest limitation you could impose on the programs to 
> make it possible to solve them all?

  I don't know, but I would bet that if you can't loop nor recurse, that's
a pretty safe bet.

-- 
                                                          - Warp

Post a reply to this message

Invisible wrote:
> - What is the "most powerful" language for which you *can* tell is an 
> arbitrary program will halt?

I forget what it's called, but basically anything with for loops instead of 
while loops does the trick. You have to rule out recursion also. 
Essentially, anything with indefinite loops is out, as far as I understand.

> Can you determine whether a particular execution path is ever 
> taken? 

No. That's called the "printing problem". Put a halt statement on that 
execution path.

> Or whether a given variable will ever be read/written?

Put a halt statement everywhere you read or write that variable.

> You can't 
> determine whether two programs do the same thing, but can you determine 
> whether one algorithm is the inverse of another? 

No, because then you could determine whether a third program does the same 
thing as the first, if they're both inverses of the same program.

See how it goes?

-- 
   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

>> - What is the "most powerful" language for which you *can* tell is an 
>> arbitrary program will halt?
> 
> I forget what it's called, but basically anything with for loops instead 
> of while loops does the trick. You have to rule out recursion also. 
> Essentially, anything with indefinite loops is out, as far as I understand.

So no GOTO then?

Basically, anything where flow control is data-dependent?

>> Can you determine whether a particular execution path is ever taken? 
> 
> No. That's called the "printing problem". Put a halt statement on that 
> execution path.

I had a feeling it might be undecidable...

>> Or whether a given variable will ever be read/written?
> 
> Put a halt statement everywhere you read or write that variable.

This too.

>> You can't determine whether two programs do the same thing, but can 
>> you determine whether one algorithm is the inverse of another? 
> 
> No, because then you could determine whether a third program does the 
> same thing as the first, if they're both inverses of the same program.
> 
> See how it goes?

Seems to me that almost anything remotely useful to know is undecidable. 
How helpful...

Post a reply to this message

Invisible wrote:

> - If you have an arbitrary program written in a Turing-complete 
> language, which properties *can* you determine, and which ones *can't* 
> you determine?

This seems relevant:

http://en.wikipedia.org/wiki/Rice%27s_theorem

Now, if only it wasn't completely incomprehensible...

Post a reply to this message

Warp wrote:
> Invisible <voi### [at] devnull> wrote:
>> So what's the smallest limitation you could impose on the programs to 
>> make it possible to solve them all?
> 
>   I don't know, but I would bet that if you can't loop nor recurse, that's
> a pretty safe bet.

You can loop if you can prove a bound on the looping; i.e., a Pascal style 
for-loop, or any loop with a loop variant (in the technical sense of that term).

You can recurse as long as you always have an upper bound on the recursion.

You can also prove it if your language disallows dynamic allocation, 
including not having unboundedly-large integers.  Think of some of the 
original microcomputer BASIC interpreters, with 26 16-bit variables to work 
with. You could still loop forever, but if you run more than 26^2^16 steps, 
you're looping.

-- 
   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:
>>> - What is the "most powerful" language for which you *can* tell is an 
>>> arbitrary program will halt?
>>
>> I forget what it's called, but basically anything with for loops 
>> instead of while loops does the trick. You have to rule out recursion 
>> also. Essentially, anything with indefinite loops is out, as far as I 
>> understand.
> 
> So no GOTO then?

Forward goto, sure. :-)

> Basically, anything where flow control is data-dependent?

No. Well, yes, in a sense. You're trying to simplify something that's 
already trivially simple, and in so doing just raising questions about what 
you mean by your version of the words.  "Indefinite loops are out." A loop 
you can't look at and tell at compile time the maximum number of times it'll 
loop is an indefinite loop. While loops are not indefinite loops if you can 
tell at compile time how often they'll loop: See Eiffel's loops, for example.

Recursion is OK as long as you have an upper bound on how often you recurse, 
somehow.

> Seems to me that almost anything remotely useful to know is undecidable. 

Only on unbounded computers.

-- 
   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?

 > for any non-trivial property of partial functions,

A partial function is one that isn't defined for every input value. The way 
you model that in a computation is to have the function not return, i.e., 
get stuck in an infinite loop.

 > there is no general and effective method

"general and effective" means it works for all inputs and always returns. 
(An "effective" function always returns an answer when computed.)

 > Here, a property of partial functions is called trivial if it holds for 
all partial computable functions or for none,

So if some partial functions have that property but not all, it's a 
non-trivial property.  A "trivial" property might be that it executes at 
least one computation, for example.

 > and an effective decision method is called general if it decides 
correctly for every algorithm.

That pretty much sums it up.

Or were you saying the proof is too confusing?


-- 
   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 wrote:
> Invisible wrote:
>> - What is the "most powerful" language for which you *can* tell is an 
>> arbitrary program will halt?
> 
> I forget what it's called, but basically anything with for loops instead 
> of while loops does the trick. You have to rule out recursion also. 
> Essentially, anything with indefinite loops is out, as far as I understand.
> 

I believe it's called a "primitive recursive" language.

This is also relevant: 
http://en.wikipedia.org/wiki/Total_functional_programming

Post a reply to this message

Kevin Wampler wrote:
> I believe it's called a "primitive recursive" language.

Yes, that rings a bell. :-)

-- 
   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

"Warp" <war### [at] tagpovrayorg> wrote in message
news:4a671eb6@news.povray.org...
> Invisible <voi### [at] devnull> wrote:

> > It's common knowledge that if you write an arbitrary program in a
> > Turing-complete programming language, it is impossible to determine
> > whether the program will ever halt.

>   That's not stated correctly. It's impossible to create an algorithm
which
> would tell for all possible programs whether they terminate or not.

Even so, one has to be careful, for it's possible to determine if any such
finite program will halt or not - just run the program until all possible
states would be exhausted.

Post a reply to this message

On 22-7-2009 18:24, Darren New wrote:
> Invisible wrote:
>>>> - What is the "most powerful" language for which you *can* tell is 
>>>> an arbitrary program will halt?
>>>
>>> I forget what it's called, but basically anything with for loops 
>>> instead of while loops does the trick. You have to rule out recursion 
>>> also. Essentially, anything with indefinite loops is out, as far as I 
>>> understand.
>>
>> So no GOTO then?
> 
> Forward goto, sure. :-)

define forward
> 
>> Basically, anything where flow control is data-dependent?
> 
> No. Well, yes, in a sense. You're trying to simplify something that's 
> already trivially simple, and in so doing just raising questions about 
> what you mean by your version of the words.  "Indefinite loops are out." 
> A loop you can't look at and tell at compile time the maximum number of 
> times it'll loop is an indefinite loop. While loops are not indefinite 
> loops if you can tell at compile time how often they'll loop: See 
> Eiffel's loops, for example.
> 
> Recursion is OK as long as you have an upper bound on how often you 
> recurse, somehow.
> 
>> Seems to me that almost anything remotely useful to know is undecidable. 
> 
> Only on unbounded computers.
> 
Perhaps also things that are decidable are not really useful to know. 
Example: you are going to die. See, not a bit of information added to 
the common knowledge, but is was decidable.

Post a reply to this message

On 22-7-2009 20:30, somebody wrote:
> "Warp" <war### [at] tagpovrayorg> wrote in message
> news:4a671eb6@news.povray.org...
>> Invisible <voi### [at] devnull> wrote:
> 
>>> It's common knowledge that if you write an arbitrary program in a
>>> Turing-complete programming language, it is impossible to determine
>>> whether the program will ever halt.
> 
>>   That's not stated correctly. It's impossible to create an algorithm
> which
>> would tell for all possible programs whether they terminate or not.
> 
> Even so, one has to be careful, for it's possible to determine if any such
> finite program will halt or not - just run the program until all possible
> states would be exhausted.

Why would the number of states be finite and why do you assume determinism?

Post a reply to this message

Am Wed, 22 Jul 2009 20:55:19 +0200 schrieb andrel:

>>> So no GOTO then?
>> 
>> Forward goto, sure. :-)
> 
> define forward

Higher adress than current one in sequential memory?

Post a reply to this message

On 22-7-2009 21:05, Florian Pesth wrote:
> Am Wed, 22 Jul 2009 20:55:19 +0200 schrieb andrel:
> 
>>>> So no GOTO then?
>>> Forward goto, sure. :-)
>> define forward
> 
> Higher adress than current one in sequential memory?
> 
Physical memory or logical?

Post a reply to this message

somebody <x### [at] ycom> wrote:
> Even so, one has to be careful, for it's possible to determine if any such
> finite program will halt or not - just run the program until all possible
> states would be exhausted.

  A finite program might never exhaust all possible states with unbounded
memory.

-- 
                                                          - Warp

Post a reply to this message

Am Wed, 22 Jul 2009 21:15:13 +0200 schrieb andrel:

> On 22-7-2009 21:05, Florian Pesth wrote:
>> Am Wed, 22 Jul 2009 20:55:19 +0200 schrieb andrel:
>> 
>>>>> So no GOTO then?
>>>> Forward goto, sure. :-)
>>> define forward
>> 
>> Higher adress than current one in sequential memory?
>> 
> Physical memory or logical?

Logical and assuming the program and the MMU doesn't do "nasty" stuff :).

Post a reply to this message

On 22-7-2009 21:27, Florian Pesth wrote:
> Am Wed, 22 Jul 2009 21:15:13 +0200 schrieb andrel:
> 
>> On 22-7-2009 21:05, Florian Pesth wrote:
>>> Am Wed, 22 Jul 2009 20:55:19 +0200 schrieb andrel:
>>>
>>>>>> So no GOTO then?
>>>>> Forward goto, sure. :-)
>>>> define forward
>>> Higher adress than current one in sequential memory?
>>>
>> Physical memory or logical?
> 
> Logical and assuming the program and the MMU doesn't do "nasty" stuff :).

I think we can safely assume that the program is in one block, or are 
there systems where parts of programs van be in more than one segment? 
Also assume that you can not execute something in a data or stack segment.
We have nearly pinned it.
Now we only have to make sure a compiler leaves the order of the 
statements in place or it knows compile time where everything will end 
up. Shouldn't be too difficult.
Codebuster's verdict: possible.

Post a reply to this message

"Warp" <war### [at] tagpovrayorg> wrote in message
news:4a676772@news.povray.org...
> somebody <x### [at] ycom> wrote:

> > Even so, one has to be careful, for it's possible to determine if any
such
> > finite program will halt or not - just run the program until all
possible
> > states would be exhausted.

>   A finite program might never exhaust all possible states with unbounded
> memory.

True in that Turing machines do have unbounded memory. Of course no real
machine does or will.

Post a reply to this message

"andrel" <a_l### [at] hotmailcom> wrote in message
news:4A6### [at] hotmailcom...
> On 22-7-2009 20:30, somebody wrote:
> > "Warp" <war### [at] tagpovrayorg> wrote in message
> > news:4a671eb6@news.povray.org...
> >> Invisible <voi### [at] devnull> wrote:
> >
> >>> It's common knowledge that if you write an arbitrary program in a
> >>> Turing-complete programming language, it is impossible to determine
> >>> whether the program will ever halt.
> >
> >>   That's not stated correctly. It's impossible to create an algorithm
> > which
> >> would tell for all possible programs whether they terminate or not.
> >
> > Even so, one has to be careful, for it's possible to determine if any
such
> > finite program will halt or not - just run the program until all
possible
> > states would be exhausted.

> Why would the number of states be finite and why do you assume
determinism?

The Turing process does not prescribe for true randomness. And with
determinism plus finite resources, states will be finite.

Post a reply to this message

somebody <x### [at] ycom> wrote:
> True in that Turing machines do have unbounded memory. Of course no real
> machine does or will.

  That doesn't make solving the halting problem any easier.

  It's like the computational complexity of algorithms: Since an algorithm
will always be run on a computer with limited resources, techincally speaking
that means that all (terminating) algorithms are O(1).

  Of course that's not useful information. It doesn't tell us anything.
The unbounded case is much more informative and useful.

-- 
                                                          - Warp

Post a reply to this message

On 22-7-2009 23:21, somebody wrote:
> "Warp" <war### [at] tagpovrayorg> wrote in message
> news:4a676772@news.povray.org...
>> somebody <x### [at] ycom> wrote:
> 
>>> Even so, one has to be careful, for it's possible to determine if any
> such
>>> finite program will halt or not - just run the program until all
> possible
>>> states would be exhausted.
> 
>>   A finite program might never exhaust all possible states with unbounded
>> memory.
> 
> True in that Turing machines do have unbounded memory. Of course no real
> machine does or will.

A Turing machine with unspecified memory size will do. 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?

Post a reply to this message

Warp wrote:
> somebody <x### [at] ycom> wrote:
>> True in that Turing machines do have unbounded memory. Of course no real
>> machine does or will.
> 
>   That doesn't make solving the halting problem any easier.

Sure it does, if you have a machine to test it on that has exponentially 
more memory than the machine it runs on.

If you have a pseudo-Turing machine with 5 states and a binary tape only 10 
symbols long, if it runs more then 5K steps, it's never going to halt.

The halting problem is specifically about Turing machines with unbounded 
memory, if that's what you mean.  (I know you know this, so I must be 
misunderstanding what you mean.)

Maybe you mean it doesn't make practical program analysis significantly 
easier to know it's only going to run on a machine with a few gigabytes of 
memory?

>   It's like the computational complexity of algorithms: Since an algorithm
> will always be run on a computer with limited resources, techincally speaking
> that means that all (terminating) algorithms are O(1).

Good thing that's not how O() is 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

andrel wrote:
>>> So no GOTO then?
>> Forward goto, sure. :-)
> define forward

Such that you never branch to an address you've already executed.

> Perhaps also things that are decidable are not really useful to know. 

Nah. It's useful to know you haven't violated the type system, and that's 
decidable.

-- 
   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 22-7-2009 23:50, Darren New wrote:
> andrel wrote:
>>>> So no GOTO then?
>>> Forward goto, sure. :-)
>> define forward
> 
> Such that you never branch to an address you've already executed.

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.


>> Perhaps also things that are decidable are not really useful to know. 
> 
> 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.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> >   It's like the computational complexity of algorithms: Since an algorithm
> > will always be run on a computer with limited resources, techincally speaking
> > that means that all (terminating) algorithms are O(1).

> Good thing that's not how O() is defined. :-)

  I think it is. The problem "sort 10 elements" can be solved in O(1).
Likewise the problems "sort 1 million elements" and "sort 10^100000 elements"
are both O(1). Any problem on a computer with limited resources is O(1).
Larger O functions come into play only when the resources are unlimited.

  However, it's not at all useful to think of algorithms as running within
limited resources. That doesn't give us any useful information. Computational
complexity analysis only gives useful information when assuming that resources
are unbounded.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>>>   It's like the computational complexity of algorithms: Since an algorithm
>>> will always be run on a computer with limited resources, techincally speaking
>>> that means that all (terminating) algorithms are O(1).
> 
>> Good thing that's not how O() is defined. :-)
> 
>   I think it is. [...]
> Larger O functions come into play only when the resources are unlimited.

I'm pretty sure O() is defined as some function whose value exceeds the 
measurement of your algorithm as n approaches infinity, with n being the 
size of the input (measured in some particular way). So O(n^2) means some 
measurement of your algorithm will eventually be and stay below k*n^2 as n 
grows without bound.

So if your input isn't unbounded, then O() doesn't make much sense. If your 
input is unbounded, then you have an unlimited amount of resources going 
into the problem, as input is one of your resources. Certainly you can't 
sort an unbounded number of elements without an unbounded amount of resources.

I.e., the way O(n) is usually defined counts "n" in memory, and "n" has to 
grow without bound.  (I.e., O(n) usually assumes "offline" work.)

>   However, it's not at all useful to think of algorithms as running within
> limited resources. That doesn't give us any useful information. Computational
> complexity analysis only gives useful information when assuming that resources
> are unbounded.

Certainly computational complexity analysis gives useful information for 
bounded workloads in the sense that an O(lg n) sort is better than an O(n^2) 
sort[1], even on smaller workloads. It's not really useful to say sorting 10 
million text lines is O(1) because you know you only have 10 million of them.


I think we're still talking silly definitions, tho. We both know what's 
going on here. :-)




[1] Modulo ridiculous constants, of course.

-- 
   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

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.

> 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. :-)

-- 
   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

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

Warp wrote:
> 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.

I'm saying O() is defined as "a function that's always bigger than *your* 
function, even as the input to your function grows without bound." If your 
input doesn't grow without bound, O() isn't well defined.

O() is defined as an asymptotic value. You can't have an asymptote of one value.

It's like asking whether you can solve the halting problem for one program I 
give you. That isn't "the halting problem", so the answer is in a completely 
different class.

-- 
   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:
> Warp wrote:
> > 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.

> I'm saying O() is defined as "a function that's always bigger than *your* 
> function, even as the input to your function grows without bound." If your 
> input doesn't grow without bound, O() isn't well defined.

> O() is defined as an asymptotic value. You can't have an asymptote of one value.

> It's like asking whether you can solve the halting problem for one program I 
> give you. That isn't "the halting problem", so the answer is in a completely 
> different class.

  I don't know why, but I'm still understanding that as "O(1) doesn't make
sense".

  The only way for an algorithm to be O(1) is that it does *not* depend on
any amount of input. You seem to be arguing that the O notation does not
describe such algorithms. Thus O(1) is nonsensical.

  But O(1) is not nonsensical. It's commonly used.

-- 
                                                          - Warp

Post a reply to this message

>> 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.

OK, so Rice's theorum applies only to the input/output behaviour of the 
program then?

Does that mean it *doesn't* apply to things like time or space usage?

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 wrote:
> OK, so Rice's theorum applies only to the input/output behaviour of the 
> program then?
> 
> Does that mean it *doesn't* apply to things like time or space usage?

Correct.  If you have any (computable) bound on the time or space usage, 
then it's easy to determine if a given program will exceed those bounds 
in computing a function by simply running it and checking (note in the 
space usage case you might have to run it exponentially longer than the 
space bound).  If the program runs too long or uses too much space, you 
can just terminate it and halt, so this property is decidable.

Post a reply to this message

>> OK, so Rice's theorum applies only to the input/output behaviour of 
>> the program then?
>>
>> Does that mean it *doesn't* apply to things like time or space usage?
> 
> Correct.  If you have any (computable) bound on the time or space usage, 
> then it's easy to determine if a given program will exceed those bounds 
> in computing a function by simply running it and checking (note in the 
> space usage case you might have to run it exponentially longer than the 
> space bound).  If the program runs too long or uses too much space, you 
> can just terminate it and halt, so this property is decidable.

Right. So if I write a pure function (i.e., some code that takes some 
input and returns some output but does nothing else - aside from maybe 
allocating memory), it is impossible to tell anything about this 
function other than how long it's going to take and how much memory it's 
going to eat?

Hmm, well that's a fairly dissapointing result. Apparently static 
analysis is an entirely hopeless endevour...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 wrote:
> Right. So if I write a pure function (i.e., some code that takes some 
> input and returns some output but does nothing else - aside from maybe 
> allocating memory), it is impossible to tell anything about this 
> function other than how long it's going to take and how much memory it's 
> going to eat?

It's slightly worse than that.  You can only *verify* a guess for the 
time/space consumption for each input you test.  It's always possible 
that the program could be entirely correct but exceed these bounds.  And 
really this is only possible through sort of a "cheat" -- there's not 
any interesting static analysis going on anywhere in this.

Doesn't mean static analysis can't be useful in practice though.

Post a reply to this message

Warp wrote:
>   I don't know why, but I'm still understanding that as "O(1) doesn't make
> sense".

You realize that in O(1), the 1 is the *output* of the analysis, right?

>   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.

> You seem to be arguing that the O notation does not
> describe such algorithms. Thus O(1) is nonsensical.

No. I'm saying O() is nonsensical if you have an algorithm that only takes a 
fixed-size input. O() isn't defined on algorithms that can't handle 
unbounded size inputs, since it's defined as how many resources an algorithm 
consumes while running on increasingly larger inputs. If it doesn't run at 
all on increasingly larger inputs, O() isn't defined.

>   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. If the answer is "it crashes with more than 10 inputs", it makes no 
sense to ask how fast the answer comes back.

 > "How many steps are needed to sort an array of 10 elements?"

That's not a question that is answered with O() notation, exactly because 
every single operation with a fixed size input runs in the same length of 
time, as far as O() is concerned. It's like asking what answer is returned 
by a function that gets stuck in an infinite loop. "Answer" isn't defined in 
that case.

You may want to say "Any algorithm that only runs on a fixed-size input I 
define as running in O(1)", but that's an addition to the defintion that 
everyone else uses.

-- 
   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

Orchid XP v8 wrote:
> OK, so Rice's theorum applies only to the input/output behaviour of the 
> program then?

Basically. It applies to the execution of an abstract program running on a 
given input. (I.e., a particular turing machine with a particular input tape.)

> Does that mean it *doesn't* apply to things like time or space usage?

I don't know.

-- 
   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:
> Warp wrote:
> >   I don't know why, but I'm still understanding that as "O(1) doesn't make
> > sense".

> You realize that in O(1), the 1 is the *output* of the analysis, right?

  I don't understand that.

> >   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")?

> >   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.

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v8 wrote:
> function other than how long it's going to take and how much memory it's 
> going to eat?

No, you can't tell how long it's going to take or how much memory it'll use. 
You can only tell if it's going to take more than X time or more than Y 
memory.  You do that by running it until it either halts or exceeds that 
limit. (And you can tell if you got in a loop using only a fixed amount of 
memory, so that's not hit by the halting problem.)

That's different from figuring out the minimum X time to doesn't take longer 
than, for example.

-- 
   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