5 citations · 16 across the 20 of their papers we have counts for
4 papers · 1 filter
The probability of a computable output from a random oracle
George Barmpalias, Douglas Cenzer, Christopher P. Porter
Consider a universal Turing machine that produces a partial or total function (or a binary stream), based on the answers to the binary queries that it makes during the computation.…
The random members of a class
Douglas Cenzer, Christopher P. Porter
We examine several notions of randomness for elements in a given class . Such an effectively closed subset of may be viewed as the set of i…
Kolmogorov complexity and generalized length functions
Cameron Fraize, Christopher P. Porter
Kolmogorov complexity measures the algorithmic complexity of a finite binary string in terms of the length of the shortest description of . Traditionally, the length o…
Random numbers as probabilities of machine behaviour
George Barmpalias, Douglas Cenzer, Christopher P. Porter
A fruitful way of obtaining meaningful, possibly concrete, algorithmically random numbers is to consider a potential behaviour of a Turing machine and its probability with respect…