On 13/10/2010 00:23, %u wrote:
snip
Yep, it needs to run in a minimal 2^n larger limited memory system (n2^n that
is).
But those two system could of course be on the same computer. My computer, for
instance, can run Halt.exe on 30bit programs :D
n2^n? Are you sure?
Here's how I worked it
== Quote from Stewart Gordon (smjg_1...@yahoo.com)'s article
On 13/10/2010 00:23, %u wrote:
snip
Yep, it needs to run in a minimal 2^n larger limited memory system (n2^n
that is).
But those two system could of course be on the same computer. My computer,
for
instance, can run
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
Manfred_Nowak svv1...@hotmail.com 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
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.
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).
--
... IXOYE
== 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).
I was looking for a way out by making
On 10/10/2010 09:16 PM, %u wrote:
Basically: because 1GB=infinity for all purposes of logical reasoning.
No no no! :D
If you'd left out logical it would have been just fine :D
I'm not even going to give ridiculous logical proof with this assumption.. no I
will not..
..
assume inf is 1GB.. No!
On 09/10/2010 18:58, %u wrote:
Just to be clear about this, the halting problem is only unsolvable for Turing
machines.
snip
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 that,
On 09/10/2010 18:58, %u wrote:
snip
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
== Quote from Stewart Gordon (smjg_1...@yahoo.com)'s article
On 09/10/2010 18:58, %u wrote:
snip
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.
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 on the pre-factor, but experience
shows that
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 on
I am not sure where exactly the line lies where people tend to use impossible
as a
synonym for a hard problem, but I agree that np might well be around that
border.
It depends on trivial, but I wouldn't call integer factorization impossible.
The point I was trying to make was that using
On 10/10/10 17:06, %u wrote:
I am not sure where exactly the line lies where people tend to use impossible
as a
synonym for a hard problem, but I agree that np might well be around that
border.
It depends on trivial, but I wouldn't call integer factorization impossible.
The point I was trying
== Quote from Norbert Nemec (norb...@nemec-online.de)'s article
On 10/10/10 17:06, %u wrote:
I am not sure where exactly the line lies where people tend to use
impossible as a
synonym for a hard problem, but I agree that np might well be around that
border.
It depends on trivial, but
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 therefore not
== 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 because the compiler does not know the memory
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
%u e...@ee.com 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
== Quote from Simen kjaeraas (simen.kja...@gmail.com)'s article
%u e...@ee.com 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
21 matches
Mail list logo