On 13/10/2010 14:17, Manfred_Nowak wrote:
Stewart Gordon wrote:
to do it for a setup with n
bits of memory, the halt analyser would need 2^n bits.
Depends on how you define memory. If registers and flags of the CPU are not
included in your definition of memory, then 2^n bits may not suffice.
Manfred_Nowak wrote:
Stewart Gordon wrote:
to do it for a setup with n
bits of memory, the halt analyser would need 2^n bits.
Depends on how you define memory. If registers and flags of the CPU are
not
included in your definition of memory, then 2^n bits may not suffice.
However, those
Stewart Gordon wrote:
> to do it for a setup with n
> bits of memory, the halt analyser would need 2^n bits.
Depends on how you define memory. If registers and flags of the CPU are not
included in your definition of memory, then 2^n bits may not suffice.
-manfred
teral.
This now makes my hatl.exe capable of 33bit programs :D
> You could take this as meaning that the halting problem is solvable
> within a certain computational class: that in which a finite but
> arbitrarily large amount of memory must be allocated at the outset.
> However, we would
t from its
address in H's memory space.
You could take this as meaning that the halting problem is solvable
within a certain computational class: that in which a finite but
arbitrarily large amount of memory must be allocated at the outset.
However, we would need to allow the amount of mem
== Quote from Stewart Gordon (smjg_1...@yahoo.com)'s article
> On 09/10/2010 18:58, %u wrote:
>
> > In the more general limited-memory setup it is actually quite simple to
> > solve
> > the Halting problem:
> > 1. Save every state of the system.
> >
On 09/10/2010 18:58, %u wrote:
In the more general limited-memory setup it is actually quite simple to solve
the Halting problem:
1. Save every state of the system.
2. If the program ends, the program Halts -> done.
2. For every state, check to if it has been saved before.
If so, the prog
On 09/10/2010 18:58, %u wrote:
Just to be clear about this, the halting problem is only unsolvable for Turing
machines.
No, it's unsolvable for any computational class that's at least as
powerful as a Turing machine. In its most general form, the
unsolvability theorem states tha
orce solution of the halting problem is
indeed theoretically possible for a finite machine, but it scales
exponentially in the memory size, resulting in a run time which is large
compared to anything that you could reasonably call "finite".
== Quote from BCS (n...@anon.com)'s article
> Hello %u,
> > Just to be clear about this, the halting problem is only unsolvable
> > for Turing
> > machines.
> More correctly, the halting problem for machine X is unsolvable by machine
> X (or any weaker machine).
Hello %u,
Just to be clear about this, the halting problem is only unsolvable
for Turing
machines.
More correctly, the halting problem for machine X is unsolvable by machine
X (or any weaker machine).
--
... <
== Quote from Norbert Nemec (norb...@nemec-online.de)'s article
> On 10/10/10 19:36, %u wrote:
> > == Quote from Norbert Nemec (norb...@nemec-online.de)'s article
> >> In language design, the theoretical halting problem actually is often an
> >> argument b
On 10/10/10 19:36, %u wrote:
== Quote from Norbert Nemec (norb...@nemec-online.de)'s article
In language design, the theoretical halting problem actually is often an
argument because the compiler does not know the memory limitation at run
time. The finite memory of the machine can therefor
; > border.
> > It depends on "trivial", but I wouldn't call integer factorization
> > impossible.
> >
> > The point I was trying to make was that using "impossible" to denote the
> > practical
> > halting problem is very confusing as
The point I was trying to make was that using "impossible" to denote the
practical
halting problem is very confusing as the theoretical Halting problem is truly
impossible.
Confusing, as the proof at first sight seems to hold on memory limited systems
as
well.
I think, the essence here is t
was that using "impossible" to denote the
practical
halting problem is very confusing as the theoretical Halting problem is truly
impossible.
Confusing, as the proof at first sight seems to hold on memory limited systems
as
well.
== Quote from Norbert Nemec (norb...@nemec-online.de)'s
On 10/10/2010 8:07 PM, Norbert Nemec wrote:
"Impossible to solve" is often used synonymous to "exponentially hard to
solve" meaning, as the problem size (e.g. size of finite memory) grows
as N, the cost for solution grows as exp(N). Of course, the actual cost
of an actual problem always depends o
ut experience
shows that exponentially hard problems are typically only solvable for
trivially small problems.
On 09/10/10 21:59, %u wrote:
== Quote from Simen kjaeraas (simen.kja...@gmail.com)'s article
%u wrote:
Just to be clear about this, the halting problem is only unsolvable for
Tu
On Sat, Oct 9, 2010 at 9:11 AM, Stewart Gordon wrote:
> On 08/10/2010 00:39, Tomek Sowiński wrote:
>
>
>> What's the halting problem?
>>
>
> Basically, it's the challenge of determining algorithmically whether an
> arbitrary algorithm given arbitrar
== Quote from Simen kjaeraas (simen.kja...@gmail.com)'s article
> %u wrote:
> > Just to be clear about this, the halting problem is only unsolvable for
> > Turing
> > machines.
> > That is, a machine with a tape that extends or is indefinitely
> > extensi
%u wrote:
Just to be clear about this, the halting problem is only unsolvable for
Turing
machines.
That is, a machine with a tape that extends or is indefinitely
extensible to
the right.[wikipedia:Turing machine]
In the more general limited-memory setup it is actually quite simple to
Just to be clear about this, the halting problem is only unsolvable for Turing
machines.
That is, a machine with a tape that extends or is indefinitely extensible to
the right.[wikipedia:Turing machine]
In the more general limited-memory setup it is actually quite simple to solve
the Halting
On 9/10/10 3:11 PM, Stewart Gordon wrote:
Personally, I think it's a shame that the halting problem can't be
solved. If it could, we could use it to solve many mathematical problems
that have as it happens remained unsolved for centuries.
But solving those problems would mean nothi
On 08/10/2010 00:39, Tomek Sowiński wrote:
What's the halting problem?
Basically, it's the challenge of determining algorithmically whether an
arbitrary algorithm given arbitrary input will eventually halt or carry
on running forever.
The point is that the halting problem is k
24 matches
Mail list logo
