Prev: Fairness: Where can it be better handled?
Next: Artificial Intelligence Discovery Generates Software Extensions Tied to Math
From: tchow on 14 May 2010 11:25
In article <852jm9FopcU1(a)mid.individual.net>,
Tim Frink <plfriko(a)yahoo.de> wrote:
>But what about real-life systems such as my Intel Linux box where I
>run e.g., C programs? These computer systems can be modeled as finite
>state machines where I could (at least in theory) test all possible
>program executions, i.e., all possible initial states and all possible
>inputs (of course in practice one runs into complexity problems). But
>this would mean that the halting problem becomes decidable, right?

The halting problem for finite-state machines is decidable, yes.

However, it's worth pointing out a slight pitfall here. One might be
tempted to argue that since real-life systems can be "reasonably" modeled
as finite-state machines, the halting problem for real-life systems is
solvable in practice (ignoring complexity issues). The trouble is that
the halting problem for finite-state machines is *not decidable by a
finite-state machine*. In other words, if you want to model all real-life
systems as finite state machines, then the halting problem for real-life
machines is decidable only by an imaginary machine, and not by a real-life
machine.

The reason that people prefer the Turing machine as a model of computation
despite its seemingly unrealistic unbounded memory is that it captures the
notion of algorithms where there's a clear concept of how to *extrapolate*
the algorithm *if* we were given more memory. No finite-state machine is
capable of recognizing when a binary string consists of a bunch of zeros
followed by an equal number of ones, because no matter how big the machine
is there will always be a really long binary string where the number of
zeros is too large for the poor finite-state machine to keep track of.
But most of us feel intuitively that this is an easy problem and not an
"uncomputable" problem because we see how to write a simple program that
will solve it, provided that it's given memory proportionate to the problem
instance that it's supposed to solve. If you feel this way then you have
already defected to the Turing machine camp from the finite-state camp.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: Tim Frink on 15 May 2010 07:29
First of all thank you for all your answers.
>
>> The halting problem for finite machines is decidable by machines with
>> exponentially more resources than the ones being modelled.
>
> Actually, twice as much memory is enough.

Why do we need twice as much memory? Once for the N states of the machine
to be tested and N states for the testing machine that has to model all
these N states?

And a practical question: how could a real machine by modeled as a finite
state machine? Do all the available resources of the machine have to be
modeled or is it sufficient to model all possible states of the available
memory into which the machine can run?
>
> If a machine with N possible states terminates, it must do so after at
> most N steps, otherwise it will have entered a loop. So to decide
> termination, you just run a copy of the machine and count the number of
> steps. If you terminate before N steps, you have proven termination. If
> not, you have proven nontermiantion.

Why is it sufficient to check just N states? If the machine runs into a
loop it may happen that some states are repeated. So, my intuition tells
me that the machine could in total visit a multiple of the N states before
terminating.

And how can the termination of such a program be determined:

main(x)
{
while(x); // repeat when x==1
}

In this case I might happen that the input x=1 is provided more than N
times to the program. So, nontermination might be wrongly assumed.

Tim
From: Jym on 16 May 2010 17:31
On Thu, 13 May 2010 18:32:06 +0200, Rick Decker <rdecker(a)hamilton.edu>
wrote:

> On 5/13/10 11:20 AM, Tim Frink wrote:
>> Hi,
>>
>> it is known that the haling problem is not decidable in general.
>>
>> When I understand it correctly, this is only true if the system where
>> the computation is performed is considered to be a turing machine (with
>> an infinite number of states and infinitely large variable values).
>>
>> But what about real-life systems such as my Intel Linux box where I
>> run e.g., C programs? These computer systems can be modeled as finite
>> state machines where I could (at least in theory) test all possible
>> program executions, i.e., all possible initial states and all possible
>> inputs (of course in practice one runs into complexity problems). But
>> this would mean that the halting problem becomes decidable, right?

> Right. The Halting Problem for finite automata is decidable, though
> a real-world computer has so many states that it might take *ahem*
> a bit of time to decide.

To make this a bit more precise:
If you have 100 bits, you have 2^100 states.
If you run this on a computer around 10GHz (not too bad even these days),
you can go through approximately 10^10 different states per second.
Going through the 2^100 states of you machine will require a time roughly
equal to the age of the universe (give or take 10%)...

Now, real computers don't have 100 bits but somewhere around 4GB RAM (that
is 2^32 bits !) and around 300GB of hard drive...
This, to speak only about personal computers. Not the huge thing used for
large computations...

--
Hypocoristiquement,
Jym.
From: Torben �gidius Mogensen on 17 May 2010 05:37
Tim Frink <plfriko(a)yahoo.de> writes:

> First of all thank you for all your answers.
>>
>>> The halting problem for finite machines is decidable by machines with
>>> exponentially more resources than the ones being modelled.
>>
>> Actually, twice as much memory is enough.
>
> Why do we need twice as much memory? Once for the N states of the machine
> to be tested and N states for the testing machine that has to model all
> these N states?

No, N states for the machine being tested and a counter that tells you
if you have been in more than N states (which implies that a state is
repeated).

If you, for example, have 100 bits of data this is 2^100 states. You
need 100 bits for a counter that can count to 2^100, so the counter
needs as much space as the state.

Torben
From: Tim Frink on 17 May 2010 13:47
> If you, for example, have 100 bits of data this is 2^100 states. You
> need 100 bits for a counter that can count to 2^100, so the counter
> needs as much space as the state.

OK, thank you.

It would be great if someone could also answer my other questions. ;-)

Regards,
Tim

First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Fairness: Where can it be better handled?
Next: Artificial Intelligence Discovery Generates Software Extensions Tied to Math