Definition of randomness (sidebar: truth is random)

[0rthodontist]

Ah, I actually didn't say what I meant there--I edited so it now reads how I intended it.

I don't think the rearrangement conveys or destroys any information because it doesn't depend on the bits in s--if I rearranged the terms to, for example, order them, then I would be reducing the amount of information, but since the rearrangement here is fixed from the start and you CAN directly derive n bits in s from n bits in t and vice versa, I think they should be looked at as the same. The bits are totally random, and s and t both have compression ratios 1.

 

[Hurkyl]

Here is a definition of a totally random string. s is a totally random string iff for any n there exists a Turing machine M with an infinite output tape that can compute the first n bits of s on input 0, but for any such machine M there exists a number m (and m > n) such that the m'th letter on the output tape of M on input 0 does not agree with the m'th letter in s.

This is equivalent to computability!

Theorem: the following are equivalent:
(1) s is not a totally random string.
(2) There exists a turing machine M with an auxiliary output tape that correctly prints the letters of s in order. (on any input)
(3) There exists a turing machine M such that M(n) is the n-th letter of s.



I imagine you're right about rearrangement -- as long as the rearrangement is computable. But to be honest, I would have thought K(xy) = O(K(x) + K(y)) at first too.

 

[0rthodontist]

(by the way after thinking about this for a bit I think that a better name for what I defined is a "random" rather than "totally random" string because the compression ratio for what I defined can be less than 1).

No, randomness as I defined it is not equivalent to noncomputability, though. Let t be an infinite binary string and let s = kt, where k is the number, printed in binary, that is the longest string that a terminating turing machine of size 20 can print. (did I get that right? I mean for k to be a finite noncomputable number). Then s is noncomputable but it is also not random as I defined it because there does not exist any machine that can compute the first |k| symbols of s.

 

[Hurkyl]

There is no such thing as a noncomputable integer. For every integer n, there exists a turing machine M such that M(w) = n for any input w.

It's the function that's noncomputable: there does not exist a turing machine M such that, for every integer n:

M(n) = the longest string that a terminating turing machine of size n can print

 

[0rthodontist]

Is there already a formal concept of a "knowable" infinite string, by which I mean a string for which any prefix can be listed explicitly and a proof exists that the listing is the prefix? I guess that such an idea would both have to refer to definitions of strings, rather than strings themselves.

 

[AKG]

One thing worth noting is that you've not really shown that the set of tautologies is undefineable. You've given a 1-1 correspondence between tautologies and a set that is undefinable. Actually, I'm not sure that you've shown this set to be undefinable, you just say that it is Tarski's theorem. What exactly does Tarski's theorem say, and what more do you say? Note that since there exists an undefinable subset of the naturals, and since any finite set is definable, there exists an uncountable undefinable subset of the naturals. The naturals themselves form a definable uncountable subset. So, the naturals can be put into a 1-1 correspondence with some undefinable set, but this says nothing about the definability of the naturals.

Also, you don't want something like f(n) = 1. A set is definable if there is some wff f(n) of one free variable (n) such that f(a) holds true in the standard model iff a is in the set. So the set {1} can be defined by the wff n=1, or more precisely, n=S0, where S is the successor function in the standard model.

 

[0rthodontist]

Is there already a formal concept of a "knowable" infinite string, by which I mean a string for which any prefix can be listed explicitly and a proof exists that the listing is the prefix? I guess that such an idea would both have to refer to definitions of strings, rather than strings themselves.

We are starting computability in my theory of computation class so I was thinking about this again. There are no knowable, noncomputable infinite strings because every knowable string can be computed by a machine that does a proof search.

Here is what I think is a better definition of randomness:
Let A and B be two sets of axioms, with A a subset of B. A string S is random in A, "given" B, if it is knowable with respect to B but not knowable with respect to A.