Infinite Sequences in Theoretical Computer Science
Infinite sequences of digits (or characters) drawn from a finite alphabet are of particular interest in theoretical computer science. They are often referred to simply as sequences or streams, as opposed to finite strings. Infinite binary sequences, for instance, are infinite sequences of bits (characters drawn from the alphabet {0,1}). The set C = {0, 1}∞ of all infinite, binary sequences is sometimes called the Cantor space.
An infinite binary sequence can represent a formal language (a set of strings) by setting the n th bit of the sequence to 1 if and only if the n th string (in shortlex order) is in the language. Therefore, the study of complexity classes, which are sets of languages, may be regarded as studying sets of infinite sequences.
An infinite sequence drawn from the alphabet {0, 1, ..., b−1} may also represent a real number expressed in the base-b positional number system. This equivalence is often used to bring the techniques of real analysis to bear on complexity classes.
Read more about this topic: Sequence
Famous quotes containing the words infinite, theoretical, computer and/or science:
“Alas, poor Yorick! I knew him, Horatio: a fellow of infinite jest, of most excellent fancy.... Where be your jibes now, your gambols, your songs, your flashes of merriment that were wont to set the table on a roar?”
—William Shakespeare (1564–1616)
“There are theoretical reformers at all times, and all the world over, living on anticipation.”
—Henry David Thoreau (1817–1862)
“What, then, is the basic difference between today’s computer and an intelligent being? It is that the computer can be made to see but not to perceive. What matters here is not that the computer is without consciousness but that thus far it is incapable of the spontaneous grasp of pattern—a capacity essential to perception and intelligence.”
—Rudolf Arnheim (b. 1904)
“We would be a lot safer if the Government would take its money out of science and put it into astrology and the reading of palms.... Only in superstition is there hope. If you want to become a friend of civilization, then become an enemy of the truth and a fanatic for harmless balderdash.”
—Kurt Vonnegut, Jr. (b. 1922)