Pseudo-Random Sequences.
Abstract
Three definitions of random binary sequences are presented. The consistency of those definitions with the laws of probability theory, and the inclusion relationship of the three sets of random sequences, are investigated. These sequences, considered as characteristic functions of sets are then placed in the Kleene arithmetical hierarchy. Some restrictions on these definitions, using Blum's complexity theory, lead to the definition of pseudo-random sequences, which can be generated effectively. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1970
- Accession Number
- AD0713852
Entities
People
- Gerald Bruere-dawson
Organizations
- Massachusetts Institute of Technology