Prev: Computer Theory Researchers: Collaborate with over 14,000 Researchers at MyNetResearch.com
Next: Turing Machine Problem
From: Heelium on 24 Jun 2010 00:40
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
3. Is an outside-world observer for another computer running the
program (using camera) or runs Server() to know that thing, in each
case halting only if it gets the signal of not halting

DoIHalt(boolean):
1. Will never return if there is a halting problem.
2. Will signal the value.

Server():
1. Will run Program() and detect if it sends no-halt signal.
2. Will return if it did.

Then, there is a helper method:
Proxy()
1. Will run the Program()
2. Will detect DoIHalt() value
3. Will display it on screen

And then, there is outside-world observer:
1. Will run the Server()
2. Will somehow react to the result

On Jun 24, 5:08 am, Tim Little <t...(a)little-possums.net> wrote:
> That's a big "if", since for the general case there is no algorithm
> that can do so.

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

The halting problem we check after being otherwise sure that our
program _should_ work on given data.

> > 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: Heelium on 24 Jun 2010 00:49
By the way, I could as well have defined that this is impossible to
say, how long it takes to solve the halting problem - we can not
define our DoIHalt to signal "I'm working" every four or eight
seconds, there is no such constant, but there is no reason, why it
shouldn't always return true or false in case the problem is solvable.

For example, let's hypothetically define:

In case the program would run longer than Universe has existed,
returning takes longer than one second.

On Jun 24, 7:40 am, 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
> 3. Is an outside-world observer for another computer running the
> program (using camera) or runs Server() to know that thing, in each
> case halting only if it gets the signal of not halting
>
> DoIHalt(boolean):
> 1. Will never return if there is a halting problem.
> 2. Will signal the value.
>
> Server():
> 1. Will run Program() and detect if it sends no-halt signal.
> 2. Will return if it did.
>
> Then, there is a helper method:
> Proxy()
> 1. Will run the Program()
> 2. Will detect DoIHalt() value
> 3. Will display it on screen
>
> And then, there is outside-world observer:
> 1. Will run the Server()
> 2. Will somehow react to the result
>
> On Jun 24, 5:08 am, Tim Little <t...(a)little-possums.net> wrote:
>
> > That's a big "if", since for the general case there is no algorithm
> > that can do so.
>
> 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. 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.
>
> The halting problem we check after being otherwise sure that our
> program _should_ work on given data.
>
> > > 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: Heelium on 24 Jun 2010 01:56
For me, there was actually a specific intuitive issue with halting
problem, which is retrospection now - it applies to myself. When
starting to do something, then I could find a task, for which I could
not say if I finish the task, however long time I had to think or try.
This is clear that when I could finish a task, I must eventually know
that I could. If I could not finish a task, then it is intuitively
reasonable to believe that after long and intelligent study I am able
to step one level up, to a metalevel, and say if I am or if I am not.
For example - am I able to solve the halting problem? It is clearly
mathematically unsolvable, but it is clearly counter-intuitive when
stated without explanation. But what is the most painful case - there
must be an answer to the problem if I am able to solve the halting
problem even in case it does not have a solution. At least, there must
be some specific class of cases, where it does not have a solution -
and this class must be defineable.

Now, to be unable to solve a task, a task must be more intelligent
than I am. Let's hypothesize that by trial and error, genetic
manipulations and evolution I can - or humankind can, indeed - raise
the intelligence indefinitely. Let's hypothesize that computer, also,
can. So there must be nothing I could not, eventually, solve as
solvable or unsolvable, as long as it is not infinitely complex. Thus,
why should there not be a case that even a halting problem can, in
some specific cases, be solved as unsolvable? And then, how could it,
in reaction, behave as solvable? It could not. Thus, there is no proof
in real world that halting problem has no general solution. In world
of computer programs, where everything must be determined, there might
be a different case - a program, which will finish in case it will
return unsolvable, thus it will be solvable instead. But if we have
this uncertainty in program's inside works, we could add an
"intelligence level" scale, where we can return "too intelligent"
instead of "halting problem". Anything too intelligent is unsolvable,
because it's too intelligent. Now the question becomes - could we
write a program, which is intelligent and able to learn, even in black
box? Then we can state that we do not know if intelligent learning has
an end-point or not; is there a definite theory or definite theories
(which make it stupid to continue learning) or not? But a program,
which is detected to be truly intelligent, has no way to not be truly
intelligent - even if it's main purpose is to detect it's intelligence
and become non-intelligent in case it has detected itself illimitedly
intelligent.

But what's the conclusion, then? In case it's impossible to definitely
detect true intelligence, it might still be possible to make
definitely clear if any program, which has it's borders, will stop
working. If it's, then, programmer's task to first make sure if her
program could be truly intelligent or not, then wait the results in
case of not, the problem could have a viable solution - any program
except true intelligence could be definitely measured as finishing or
not finishing by halting problem solver, which is as intelligent as
possible (and no problem itself could not be more intelligent, but it
could be as intelligent as the solver). But there is no logical
reason, why the solver could not detect if the application is as
intelligent as itself - or even more intelligent.

How to express this in C++? [which should be the problem]

The only way - let's suppose that we have a problem solver with
constantly growing intelligence. With every step of intelligence
growth, it can solve halting problems two times faster. For every
given problem it might give up and it's also unable to be sure if it
will eventually find the final solution - or, by proof, it knows that
it does not. But it does not prove that programmer can not write the
"seed program" at once.
From: Heelium on 24 Jun 2010 04:08
I did seek further if there is some humanly wording to this logical
game.

Thus, if it's so:

DoesHalt() is a function called by program to check if it reaches a
given execution point, which will halt if the result is ambivalent.

This produces a pattern:

However we call DoesHalt() in program code, it will halt in case the
correct result depends on it.

As far as I have checked it - and the possibilities are numerous - I
get the following odd pattern:

1. If not DoesHalt(), goto 3
2. If DoesHalt(), loop forever; otherwise halt
3. Print "Forever loop"

Now, as DoesHalt will halt if there is ambivalence:

DoesHalt() on line 2 will produce forever loop inside DoesHalt()
function. This makes the behaviour of it consistent.

DoesHalt() on line 1, anyway, has a logical possibility to now assume
that line 2 will not halt, thus jump to 3.

Now, in such formal sight to things - is this somehow possible that
the loop at 2 could actually be detected only inside same computer
(because when you try to do thing on line 1. from another computer,
watching the output, you will not be sure in things) and that an
application checking the case must have metalevel access to the whole
picture - because you can not make any conclusion on line 2., where
you do not see both halting check function and the tricky code?

This looks like ...make even too much sense :P Like formally saying
that DoesHalt() must have access to it's own code instance to be sure.
From: Paul E. Black on 24 Jun 2010 14:32
On Wednesday 23 June 2010 21:24, Joshua Cranmer wrote:
> 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).
>
> [[PEB]] 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.

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.black(a)acm.org)
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