Prev: Computer Theory Researchers: Collaborate with over 14,000 Researchers at MyNetResearch.com
Next: Turing Machine Problem
From: Heelium on 23 Jun 2010 19:50
Hello!

I have, again and again, thought over halting problem for years.

I think the solution would be achieved by swapping the caller and the
called - the halting problem detector will not return any result, but
it will start a process, which knows if the caller would stop.

The process called will know that data and has no way to send back any
data - and the caller, thus, will continue the normal execution. The
caller is not allowed to get any outside information otherwise!

This removes the uncertainty. It does not prove that you can check the
execution finish.

This disproves the "you can never know if program halts" problem. In
finite state machine like computer with limited memory spaces, you can
always know - otherwise, we don't know.

Tambet
From: Heelium on 23 Jun 2010 21:01
There is also one theorem I would state:

If we can calculate before running an application, how much memory it
maximally takes, we can always check if it returns. The rest is an
optimization (which could be complex and sometimes impossible to get
some specific check into taking reasonably few amounts of memory).

I once did a program, which allowed to run some code and checked
values of variables all time, putting them into a map, where the whole
memory was key. When there was already such item, it reported no-
return; when memory was full, it reported memory-full, otherwise it
reported nice finish. But we need to check theoretical programs, not
practical ones. But we already know their input, when checking!

Thus:
If you are able to find a formulae for maximum memory need, you can
check for exit.
If you are not able to find a formulae for maximum memory need, you
don't care if it theoretically exits (assuming that you already have
the computer powerful enough to check if it does).

Thus, halting problem is at least not important. Mathematically we
need to know things like formulae of primes (or impossibility of
formulae, which returns primes for so long that we couldn't reach that
point easily) and many other things to solve the rest - someone might
do it, but it does not seem a single problem anymore. So, this theorem
is relevant.

Tambet
From: Joshua Cranmer on 23 Jun 2010 21:24
On 06/23/2010 09:01 PM, Heelium wrote:
> If you are not able to find a formulae for maximum memory need, you
> don't care if it theoretically exits (assuming that you already have
> the computer powerful enough to check if it does).

Several static analysis problems are known to be equivalent to the
halting problem (including, crucially, pointer aliasing). Bounding the
maximum memory on real-world programs would likely be insanely
difficult, and I suspect that it is equivalent to the halting problem in
difficulty.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
From: Tim Little on 23 Jun 2010 22:08
On 2010-06-24, Heelium <qtvali(a)gmail.com> wrote:
> If we can calculate before running an application, how much memory
> it maximally takes, we can always check if it returns.

That's a big "if", since for the general case there is no algorithm
that can do so.


> If you are not able to find a formulae for maximum memory need, you
> don't care if it theoretically exits (assuming that you already have
> the computer powerful enough to check if it does).

This makes no sense.


- Tim
From: BJS on 23 Jun 2010 22:40
For what it's worth, I was just reading about linear bounded automata,
which I believe are a closer representation of a computer in the real
world.

On Jun 23, 9:01 pm, Heelium <qtv...(a)gmail.com> wrote:
> There is also one theorem I would state:
>
> If we can calculate before running an application, how much memory it
> maximally takes, we can always check if it returns. The rest is an
> optimization (which could be complex and sometimes impossible to get
> some specific check into taking reasonably few amounts of memory).
>
> I once did a program, which allowed to run some code and checked
> values of variables all time, putting them into a map, where the whole
> memory was key. When there was already such item, it reported no-
> return; when memory was full, it reported memory-full, otherwise it
> reported nice finish. But we need to check theoretical programs, not
> practical ones. But we already know their input, when checking!
>
> Thus:
> If you are able to find a formulae for maximum memory need, you can
> check for exit.
> If you are not able to find a formulae for maximum memory need, you
> don't care if it theoretically exits (assuming that you already have
> the computer powerful enough to check if it does).
>
> Thus, halting problem is at least not important. Mathematically we
> need to know things like formulae of primes (or impossibility of
> formulae, which returns primes for so long that we couldn't reach that
> point easily) and many other things to solve the rest - someone might
> do it, but it does not seem a single problem anymore. So, this theorem
> is relevant.
>
> Tambet

 |  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