Prev: Computer Theory Researchers: Collaborate with over 14,000 Researchers at MyNetResearch.com
Next: Turing Machine Problem
From: Tim Little on 24 Jun 2010 22:16
On 2010-06-24, Heelium <qtvali(a)gmail.com> wrote:
> By the way - maybe an exponent powers were the function, which
> converges always to higher point than any other function?

It doesn't. The Ackermann numbers grow insanely faster than
exponential powers, for example. For example, the 4th Ackermann
number is roughly 2^2^10^19729, and the fifth is simply too large to
be directly expressed in terms of iterated powers in any sane amount
of space. And yet there are infinitely many recursive functions that
grow faster than Ackermann's.

The Busy Beaver function, which is related to the amount of space
required for programs that always halt, grows faster than *all* of
those infinitely many recursive functions. There is no algorithm to
compute the Busy Beaver function.


- Tim
From: Heelium on 25 Jun 2010 02:34
On Jun 25, 4:35 am, Tim Little <t...(a)little-possums.net> wrote:
> On 2010-06-24, Heelium <qtv...(a)gmail.com> wrote:
>
> > You see:
>
> > Program():
> > 1. Will run
> > 2. Will call an DoIHalt(boolean), which knows, if the caller would
> > stop - meanwhile it won't continue running itself
>
> I suggest instead calling WhatAreNextWeeksLotteryNumbers().  Both are
> impossible to write, but the latter would be more immediately useful.

I have a program, which could do that for any small program. I could
write, say, a JavaScript add-on, which detects all hangs in fixed-
memory functions.

> There are many problems that cannot be solved with such constraints.
> It is not even decidable in general whether any given problem is one
> of those.

Yes, but that wont apply for most normal programs.

And second - we speak about algorithms, not problems.

> Really?  It is not terribly difficult to craft a 1 MB jpeg image that
> will cause essentially any image editor to use a lot more than 4 GB of
> data for some routine editing operations - or fail to carry out the
> operation at all.

Ok, I rephrase: pixel size is what I meant.

> - Tim

From: Heelium on 25 Jun 2010 02:34
On Jun 25, 5:16 am, Tim Little <t...(a)little-possums.net> wrote:
> On 2010-06-24, Heelium <qtv...(a)gmail.com> wrote:
>
> > By the way - maybe an exponent powers were the function, which
> > converges always to higher point than any other function?
>
> It doesn't.  The Ackermann numbers grow insanely faster than
> exponential powers, for example.  For example, the 4th Ackermann
> number is roughly 2^2^10^19729, and the fifth is simply too large to
> be directly expressed in terms of iterated powers in any sane amount
> of space.  And yet there are infinitely many recursive functions that
> grow faster than Ackermann's.
>
> The Busy Beaver function, which is related to the amount of space
> required for programs that always halt, grows faster than *all* of
> those infinitely many recursive functions.  There is no algorithm to
> compute the Busy Beaver function.
>
> - Tim

ok
From: Heelium on 25 Jun 2010 02:37
On Jun 25, 5:16 am, Tim Little <t...(a)little-possums.net> wrote:
> The Busy Beaver function, which is related to the amount of space
> required for programs that always halt, grows faster than *all* of
> those infinitely many recursive functions.  There is no algorithm to
> compute the Busy Beaver function.

Lack of that algorithm does not matter.

In real world we have real computers with limited memory - we actually
target only those. And for them we have algorithms, which have some
upper limit.

Anyway, that Turings undecideability proof is disproved by me. Why you
think there is no general case algorithm?
From: Tim Little on 25 Jun 2010 03:55
On 2010-06-25, Heelium <qtvali(a)gmail.com> wrote:
> On Jun 25, 4:35 am, Tim Little <t...(a)little-possums.net> wrote:
>> I suggest instead calling WhatAreNextWeeksLotteryNumbers(). Both are
>> impossible to write, but the latter would be more immediately useful.
>
> I have a program, which could do that for any small program. I could
> write, say, a JavaScript add-on, which detects all hangs in fixed-
> memory functions.

You need to decide whether you're talking about practice or theory.
In theory, you could do that. But in theory, almost all useful
functions are not fixed-memory.

In practice, I can easily write a fixed-memory function for which your
add-on would fail before returning a correct result.


>> There are many problems that cannot be solved with such
>> constraints. It is not even decidable in general whether any given
>> problem is one of those.
>
> Yes, but that wont apply for most normal programs.

As you have already seen, even the simple task of editing JPEG-encoded
images can blow out to unexpectedly large space requirements. There
are even simpler "normal" problems for which nobody knows what the
upper bound on memory use would be.


> And second - we speak about algorithms, not problems.

We use algorithms to solve problems. For some problems, there do not
exist algorithms solving them that conform to your restrictive bounds.
For some others, we do not know if there exist such algorithms.


> Ok, I rephrase: pixel size is what I meant.

You had also better specify what image editing operations are allowed.
I can think of a few that potentially require large amounts of memory
to work correctly.


- Tim
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Computer Theory Researchers: Collaborate with over 14,000 Researchers at MyNetResearch.com
Next: Turing Machine Problem