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

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