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:
“Age cannot wither her, nor custom stale
Her infinite variety. Other women cloy
The appetites they feed, but she makes hungry
Where most she satisfies.”
—William Shakespeare (1564–1616)
“The hypothesis I wish to advance is that ... the language of morality is in ... grave disorder.... What we possess, if this is true, are the fragments of a conceptual scheme, parts of which now lack those contexts from which their significance derived. We possess indeed simulacra of morality, we continue to use many of the key expressions. But we have—very largely if not entirely—lost our comprehension, both theoretical and practical, of morality.”
—Alasdair Chalmers MacIntyre (b. 1929)
“Family life is not a computer program that runs on its own; it needs continual input from everyone.”
—Neil Kurshan (20th century)
“May we not assure ourselves that whatever woman’s thought and study shall embrace will thereby receive a new inspiration, that she will save science from materialism, and art from a gross realism; that the “eternal womanly shall lead upward and onward”?”
—Louisa Parsons Hopkins, U.S. scientist and author. As quoted in The Fair Women, ch. 16, by Jeanne Madeline Weimann (1981)