2
$\begingroup$

Given that any implementable algorithm has a finite number of internal states, and given that any state is determined by the previous one, does that implies that any algorithm loops at some point? If I run the algorithm until the number of state transitions is greater than the number of internal states, by the pigeonhole principle, I should eventually get into a loop. Is that correct?

$\endgroup$
3
$\begingroup$

You are technically correct. A modern practical computer has finitely many states, and so any program it runs will eventually repeat a state.

However, I would like to warn against interpreting this observation in the wrong way. It is not a problem in practice. The number of possible states is huge (it's huuuuuuuuuuuuuuuuuuuuge). Algorithms that are designed for machines with infinite resources (such as Turing machines) typically run just fine on a modern computer. Of course, they may use up all available memory if they are especially memory-intensive, but that's different from them cycling because they somehow repeated a configuration due to computer limitations. And when programs do cycle forever unintentionally, it is not the limited size of the computer that does it, but rather programming errors.

It is more practical to mathematically model modern computers as if they have unlimited memory than to model them as finite-state machines. This situation is a bit like modelling in physics: classical fluid dynamics models a discrete system of atoms as if it were a continuous one.

$\endgroup$
0
$\begingroup$

Consider the following algorithm:

  • $n \gets 0$
  • repeat: $n \gets n+1$

The algorithm runs for infinitely many steps without repeating the same state.

$\endgroup$
  • $\begingroup$ I mean implementable algorithm on a real machine. On a real machine, memory is finite, hence the number of possible internal states is finite. The assumption here is a finite number of internal states (e.g. Turing machine with a finite number of symbols and tape $\endgroup$ – Gianluca Ghettini Dec 9 '19 at 16:33
  • 1
    $\begingroup$ By an algorithm we usually mean a theoretical construct which is not limited in any way. If you limit your algorithm artificially to have finitely many possible states, then what you wrote is correct. $\endgroup$ – Yuval Filmus Dec 9 '19 at 16:34
  • $\begingroup$ @Gianluca Ghettini: Provided that by "finite" you mean "of a bounded and input-independent size" (which is the case for real-life computers), then Turing machines with finite amount of symbols and tape are computationally equivalent to (deterministic) finite automata. $\endgroup$ – eru-cs Dec 9 '19 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.