> This post is mostly AI generated, of course with significant guidance, feedback, iteration and some edits from me.
I can tell, because it is garbage.
AI's notion of PK is useless because of Blum's speedup theorem. Because the invariance theorem fails in PR (PR is not universal), description-length gaps between PR and Turing complete languages can grow without bound.
Essentially a more expressive formalism can encode an interpreter for the weaker one and then diagonalise over it. Restricting yourself to a total language, you sacrifice potentially unbounded conciseness.
This is a profound difference between TC and non-TC languages, and it manifests even for terminating functions. It's not just that a TC languages can encode non-terminating computations, it's that a TC language can encode terminating functions more efficiently than a non-TC language. A terminating program expressed in a total language must manifest its termination proof in a strict way with finite degrees of freedom, whatever the choice of total language might be. In a TC language it doesn't have this artificial constraint.
In some sense, as program complexity grows (expressed in a total language), more and more of the program is dedicated just to encoding its own termination proof. We can sort of see this a corollary of this experimentally with programs (proofs) written in theorem provers like Coq (which are total). Giant proofs extract to very small programs. We don't see the sort of phenomenon in theorem provers using a Curry-style type system, for example Nuprl, where the underlying lambda calculus is Turing complete. This is experimental evidence that even though most interesting functions might be PR, a PR language might not be the best language to express those functions. And this seems to be the case even without choosing specially-crafted pathological examples.
These are subtle issues and I can't fault the author for not knowing about them, but I can fault him for using AI to appear to say something profound when all that was said was woefully naïve.
Since the author seems to be concerned about tractable inductive inference, and to be honest computability does not give you much, what do you think about the utility of notions like resource-bounded Kolmogorov complexity for that?
This post argues that because most functions we encounter are primitive recursive, Primitive Kolmogorov complexity is widely applicable. I think you also need to argue that it is a meaningful notion of complexity.
PK may be very differently shaped from normal Kolmogorov complexity because you can find primitive recursive functions whose implementation in a primitive recursive programming language is arbitrarily larger than their implementation in a Turing complete programming language.
That said, I’m not sure what if anything this implies about AI.
> The uncomputability of both arises directly from the Halting Problem
This is perhaps pedantic, but this statement is a little misleading. Kolmogorov complexity and the halting problem both describe the same concept in different formulations. One could just as easily say that the halting problem arises directly from Kolmogorov complexity.
S can't be arsed to define itself. K is a measure of s (an object). What on earth is S? Is it the result of using Solomonoff induction ... on a hypothesis based on K?
Then we suddenly get the science bit:
"Whilst we might one day care about the sort of intelligence that is defined as a full "search over turing machines", for today's real world practical general intelligence, a "search over primitive recursive functions" is likely sufficient."
So, sod the Halting problem, with some sleight of hand (waving) we get AGI tomorrowish or something.
The author seems to forget that "intelligence" might eventually be defined by a "full search over turing machines" and "practical general intelligence" is not a particularly useful system and merely the description for a next token guesser and the like.
It might be computable, but is it practical? It sounds like it requires a stack of exponentials in compute time, and is impractical even for very short messages.
> This post is mostly AI generated, of course with significant guidance, feedback, iteration and some edits from me.
I can tell, because it is garbage.
AI's notion of PK is useless because of Blum's speedup theorem. Because the invariance theorem fails in PR (PR is not universal), description-length gaps between PR and Turing complete languages can grow without bound.
Essentially a more expressive formalism can encode an interpreter for the weaker one and then diagonalise over it. Restricting yourself to a total language, you sacrifice potentially unbounded conciseness.
This is a profound difference between TC and non-TC languages, and it manifests even for terminating functions. It's not just that a TC languages can encode non-terminating computations, it's that a TC language can encode terminating functions more efficiently than a non-TC language. A terminating program expressed in a total language must manifest its termination proof in a strict way with finite degrees of freedom, whatever the choice of total language might be. In a TC language it doesn't have this artificial constraint.
In some sense, as program complexity grows (expressed in a total language), more and more of the program is dedicated just to encoding its own termination proof. We can sort of see this a corollary of this experimentally with programs (proofs) written in theorem provers like Coq (which are total). Giant proofs extract to very small programs. We don't see the sort of phenomenon in theorem provers using a Curry-style type system, for example Nuprl, where the underlying lambda calculus is Turing complete. This is experimental evidence that even though most interesting functions might be PR, a PR language might not be the best language to express those functions. And this seems to be the case even without choosing specially-crafted pathological examples.
These are subtle issues and I can't fault the author for not knowing about them, but I can fault him for using AI to appear to say something profound when all that was said was woefully naïve.
Since the author seems to be concerned about tractable inductive inference, and to be honest computability does not give you much, what do you think about the utility of notions like resource-bounded Kolmogorov complexity for that?
This post argues that because most functions we encounter are primitive recursive, Primitive Kolmogorov complexity is widely applicable. I think you also need to argue that it is a meaningful notion of complexity.
PK may be very differently shaped from normal Kolmogorov complexity because you can find primitive recursive functions whose implementation in a primitive recursive programming language is arbitrarily larger than their implementation in a Turing complete programming language.
That said, I’m not sure what if anything this implies about AI.
> The uncomputability of both arises directly from the Halting Problem
This is perhaps pedantic, but this statement is a little misleading. Kolmogorov complexity and the halting problem both describe the same concept in different formulations. One could just as easily say that the halting problem arises directly from Kolmogorov complexity.
More generally, both are cases of a diagonal argument.
"K and S and are not calculable"
S can't be arsed to define itself. K is a measure of s (an object). What on earth is S? Is it the result of using Solomonoff induction ... on a hypothesis based on K?
Then we suddenly get the science bit:
"Whilst we might one day care about the sort of intelligence that is defined as a full "search over turing machines", for today's real world practical general intelligence, a "search over primitive recursive functions" is likely sufficient."
So, sod the Halting problem, with some sleight of hand (waving) we get AGI tomorrowish or something.
The author seems to forget that "intelligence" might eventually be defined by a "full search over turing machines" and "practical general intelligence" is not a particularly useful system and merely the description for a next token guesser and the like.
It might be computable, but is it practical? It sounds like it requires a stack of exponentials in compute time, and is impractical even for very short messages.
The time bound would be a non-PR function, so yeah.
Great, now please ask the AI how to calculate it for me.