Prev: Fairness: Where can it be better handled?
Next: Artificial Intelligence Discovery Generates Software Extensions Tied to Math
From: Tim Frink on 17 May 2010 13:53

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

But why is it sufficient to go just through all the states? If the program
contains loops, some states will be entered multiple times. Hence, more
than 2^100 would be entered before possibly finally terminating the
program.
From: Barb Knox on 17 May 2010 16:15
In article <85de5bF1vaU2(a)mid.individual.net>,
Tim Frink <plfriko(a)yahoo.de> wrote:

> > 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%)...
>
> But why is it sufficient to go just through all the states? If the program
> contains loops, some states will be entered multiple times. Hence, more
> than 2^100 would be entered before possibly finally terminating the
> program.

A state here represents *everything* that can be different during the
computation. For example, there is no external input (such as you used
in a previous example). The next state is a deterministic function of
the current state. So, once the machine returns to a previous state,
it's in a loop forever.

--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum videtur.
| BBB aa a r bbb |
-----------------------------
From: Tim Little on 17 May 2010 21:00
On 2010-05-17, Tim Frink <plfriko(a)yahoo.de> wrote:
> But why is it sufficient to go just through all the states? If the
> program contains loops, some states will be entered multiple
> times.

In this discussion we are using the term "state" to include everything
relevant to program execution. A deterministic machine that enters
the same state twice will loop forever, because every step between the
two occurrences will be repeated.

E.g. for a finite-tape Turing machine, the overall state includes the
sequence of symbols on the tape and the head position as well. That's
why the size of the machine state for real computers has to include
hard drives and memory as well as CPU registers and so on.

Though once you get into multithreaded programs running on CPUs with
independently clocked cores, it becomes less reasonable to use a
purely deterministic model. There exists the possibility of race
conditions depending upon arbitrary small differences in timing.


- Tim
From: Tim Frink on 18 May 2010 03:33
> In this discussion we are using the term "state" to include everything
> relevant to program execution. A deterministic machine that enters the
> same state twice will loop forever, because every step between the two
> occurrences will be repeated.
>
> E.g. for a finite-tape Turing machine, the overall state includes the
> sequence of symbols on the tape and the head position as well. That's
> why the size of the machine state for real computers has to include hard
> drives and memory as well as CPU registers and so on.

OK, that's clear now.

In one of my previous posts, I mentioned a program like this:

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

Here the termination depends on the input that is unknown. Are such input-
dependent programs also considered for the halting problem? I mean here we
can only judge if the program terminates when the program input is known.

Tim
From: Torben �gidius Mogensen on 18 May 2010 09:39
Tim Frink <plfriko(a)yahoo.de> writes:


> In one of my previous posts, I mentioned a program like this:
>
> main(x)
> {
> while(x); // repeat when x==1
> }
>
> Here the termination depends on the input that is unknown. Are such input-
> dependent programs also considered for the halting problem? I mean here we
> can only judge if the program terminates when the program input is known.

A variant of the halting problem is "Does this program terminate for all
possible inputs?". They are both undecidable for Turing machines (and
other Turing-complete language). For a finite automata (with a fixed
buound on input size), both are decidable by a larger finite automata,
but the actual resources required are larger for the more general
question.

Both variants are instances of the more general Rice's theorem:

Any nontrivial question that you ask about the semantics (input/output
function) of programs in a turing-complete language are undecidable.
Trivial questions are those that can be answered yes for all programs
and those that can be answered no for all programs.

Halting is part of the semantics (considering nontermination a special
value), so the halting problem is an instance of Rice's theorem. Other
instances are:

- Is there any input that makes the program return 42?

- Will this program return 42 when run with this particular input?

- Is the program equivalent to this other program?

Torben
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