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:
“One who pressed forward incessantly and never rested from his labors, who grew fast and made infinite demands on life, would always find himself in a new country or wilderness, and surrounded by the raw material of life. He would be climbing over the prostrate stems of primitive forest-trees.”
—Henry David Thoreau (1817–1862)
“There are theoretical reformers at all times, and all the world over, living on anticipation.”
—Henry David Thoreau (1817–1862)
“The archetype of all humans, their ideal image, is the computer, once it has liberated itself from its creator, man. The computer is the essence of the human being. In the computer, man reaches his completion.”
—Friedrich Dürrenmatt (1921–1990)
“He who would do good to another must do it in Minute Particulars:
General Good is the plea of the scoundrel, hypocrite, and flatterer,
For Art and Science cannot exist but in minutely organized Particulars.”
—William Blake (1757–1827)