The question was asked on this page
but I was not allowed to answer due to lack of reputation. Yet I wonder if my mathematical answer that follows is acceptable to philosophers.
I will limit myself to the finite strings of 0s and 1s. We say that such a string is reducible if there is a program that generates it and which is shorter than the string itself. We define the length of a program as the length of the shortest string of 0s and 1s that encodes that program.
A string is random if it is not reducible, i.e. if the shortest program that generates it is at least as long as the string itself (i.e. you cannot describe a string more concisely than simply stating it).
A finer analysis is: a string is additively k-reducible if there is a program that generates it and which is k shorter than the string itself, it is multiplicatively k-reducible if there is a program that generates it and which is k times shorter than the string itself, and it is strongly k-reducible if there is a program which generates it and which is shorter than k.
Since there are 1 + 2 + 2 *2 + 2 *3 + 2 *4+ … = 2 *n -1 < 2 *n strings shorter than n, it follows there are less than 2 *(n-k) strings shorter than n-k, there are less than 2 *(n/k) strings shorter than n/k and less than 2 *k strings shorter then k. Thus, the ratio of additive, multiplicative and strongly reducible strings to all strings is 2 *(n-k)/2 *n, 2 *(n/k)/2 *n and 2 *k/2 *n which is less than 0.001 for k>10. In short, a negligible number of strings is reducible in any of these meanings.
Imagine now a formalized theory (this can be ZFC in which we can formalize all existing mathematics) and in which we are proving the reducibility claims about strings (the statements of the form “string w can be generated by a program of length <,>,= n”) and the related program: Generate statements of that theory and check whether they are proofs of the statement “the string w cannot be generated by a program shorter than k+1” where k is the length of the shortest code of that program.
If that program stops on some string w then that string cannot be generated by a program shorter than k+1, but our theory which is a program of length k generates it, which is a contradiction. Thus, the formal theory of length k cannot prove that strings cannot be generated by programs shorter than k, if they really cannot be generated by them. But such are almost all strings because there are only finitely many of those that can be generated by programs shorter than k.
Thus, for no such string can we prove that it is irreducible even though almost all of them are. In other words, almost all such strings are random, although we cannot prove this for any of them.