September 23, 2012
General / Today's Thoughts on Algorithmic Information Theory
I know this won't make a lot of sense to most people, but I thought I needed to store these thoughts in a more permanent place before I forget them. I've been reading a paper today on Algorithmic Information Theory, and it make me think these thoughts (most of which are probably ill-founded):
- Is the Chaitin halting probability really a probability? In other words, if I have the first 5 bits of omega, does this mean that a random sampling of all programs will really match this value to some extent?
- To what extent is self-delimiting programs an intrinsic part of AIT, vs just a cheap trick to get the math right? It makes sense simply because you need the program length. But on the other hand, if omega is a probability, it seems like having the program length pre-coded would do a number on its interpretation as a probability.
- If log2(2^w) is w, is perhaps log2(w) = c? Is c the complexity number I'm looking for for my axioms?
- Is it possible to express the idea of a formal relationship to be the relationship between the algorithmic specification and its logical depth? I.e. we should expect a material cause when logical depth is low, but a formal one when logical depth is high? Could this be expressed as a ratio?
- Algorithmic complexity on partial specifications. The word "red", as implemented in 12 pt font or written in the clouds. Perhaps the partial specification is something that can be detected non-algorithmically, via an Oracle machine? In other words, instead of "give me the Xth object that matches specification X, you say, give me *an* object that matches specification X. It does not require an iteration over the whole of infinity, but a potentially large part of it very quickly. Or, perhaps, it drops it a level of Cantorian infinity.
- Recognizers vs generators = P/NP problem = logical depth vs algorithmic complexity
- What is the relationship between the constant given in AIT vs expressibility of language? In other words, if C is small, then it is easier to express random strings, at the penalty of having no easily expressible strings. A larger C will permit more compressibility. This might also be usable, at least in theory, to determine the total number of "special" strings available.
- How can algorithmic information theory be expanded for programs that take arguments? (note - number of arguments shouldn't matter, only whether one of them is itself a program, perhaps? or if the result is a program? Maybe what the Wolfram class of the argument is?)
- Might semantics and apobetics be higher Turing degrees?
- Might ethical norms be an expression of compressibility across Turing degrees?
- What about bad plans? Is it possible to state, even in abstract, non-determinable terms, what a bad plan is?