Prev: Computer Theory Researchers: Collaborate with over 14,000 Researchers at MyNetResearch.com
Next: Turing Machine Problem
From: Heelium on 24 Jun 2010 16:23
This is true, what you talk about. I have done quite a much of work to
find definitive ways to know this upper memory limit - but for now, I
can only say that this must be given.

At first, we can always know if we do not have this upper memory
limit; secondly, our program will always halt if there is no such
integer; third, this is a constraint to programmer, not a program.

For calculating upper memory limit, we must add those calculations to
an algorithm, until we reach some simplicity level, which is proven to
finish. I think we know, which mathematical function is the fastest-
growing (didn't it have something to do with e?).

I mean:
First we find an algorithm, which calculates the upper memory limit.
If this itself uses non-constant memory amount, we calculate it's
upper memory limit.
We repeat, until we find some upper memory limit, which can be simply
calculated from constants.

Then we write:
RequestMemory(500);
Calculate limit into m1 so that calculation is in 500 byte boundaries.
RequestMemory(m1);
Calculate limit into m2 so that calculation is in m1 byte boundaries.
RequestMemory(m2);
and so on, until we reach our program, which has at least as much
memory as it needs.

Such a sequence always gives result, for which we can say that it will
halt.

In case we do not know this upper memory limit, we at least know that
our algorithm is missing a critical part to be proven as halting.

On Jun 24, 9:32 pm, "Paul E. Black" <p.bl...(a)acm.org> wrote:
> Consider the Collatz conjecture: if the number is even, half it.  If
> the number is odd, multiply by 3 and add 1.  
>    http://en.wikipedia.org/wiki/Collatz_conjecture
> Since we don't know if every sequence is bounded (and big numbers take
> a lot of memory to represent), we can't predict the maximum memory for
> computing the hailstone sequence starting from a number.  That is,
>    M(n)
> where M() is the number of bits needed to compute the hailstone
> sequence starting with n.
>
> M(1) = 1
> M(2) = 2
> M(3) = 4 (max is 10)
> M(4) = 3
> M(5) = 4 (max is 16)
> M(6) = 4 (max is 10)
> M(7) = 5 (max is 52)
> M(8) = 3
> M(9) = 5 (max is 52)
> M(10) = 4
> M(11) = 5 (max is 52)
> M(12) = 4
> M(13) = 5 (max is 40)
> M(14) = 5 (max is 52)
>
> -paul-
> --
> Paul E. Black (p.bl...(a)acm.org)
From: Joshua Cranmer on 24 Jun 2010 17:02
On 06/24/2010 04:23 PM, Heelium wrote:
> I think we know, which mathematical function is the fastest-
> growing (didn't it have something to do with e?).

There is no fastest-growing function. You could compose it with a
function like Ackermann's and make it grow even faster.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
From: Heelium on 24 Jun 2010 17:12
On Jun 25, 12:02 am, Joshua Cranmer <Pidgeo...(a)verizon.invalid> wrote:
> On 06/24/2010 04:23 PM, Heelium wrote:
>
> > I think we know, which mathematical function is the fastest-
> > growing (didn't it have something to do with e?).
>
> There is no fastest-growing function. You could compose it with a
> function like Ackermann's and make it grow even faster.
>
> --
> Beware of bugs in the above code; I have only proved it correct, not
> tried it. -- Donald E. Knuth

Ok, then I was wrong with my rough memory ;)

Anyway, I would put it that way:
1. Any program with indefinite memory need will not halt.
2. This is a constraint for a programmer to calculate the memory need
of a program on given input.

The problem becomes, thus, a much stricter one - if you do not know
this memory limit, you can not use the general case solver of mine
(but my disproof allows solvers, which do not have such restrictions).
Anyway, when you are able to pass the test, you know that it will
halt; if you are not, there must always exist that integer, which
allows you to do the check.
From: Heelium on 24 Jun 2010 17:14
> > There is no fastest-growing function. You could compose it with a
> > function like Ackermann's and make it grow even faster.

By the way - maybe an exponent powers were the function, which
converges always to higher point than any other function? In such
case, combining wont help - it's most exponential, not the fastest
growing. It's growth is the fastest growing.
From: Tim Little on 24 Jun 2010 21:35
On 2010-06-24, Heelium <qtvali(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.


> We assume that it's a good style for a programmer to know that his
> program can run, say, on 4GB of memory with given data.

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.


> For example, when I can not be sure that my image editor might not
> be able to edit _some_ 1MB jpg image on my computer because of
> memory limit, I would consider this undone work.

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.

This is not a fault in those programs, it is due to the fact that a
1 MB JPEG file is capable of encoding an enormous image.


There are operations that can be bounded in space required, and in
fact JPEG image editing is one of them. However the upper bounds are
much higher than you think, and there are some operations that cannot
be bounded by any algorithm at all.


- 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