6 ms·

It can be sort of unintuitive how the concept of computability necessarily involves infinity. For example: does there exist an algorithm that computes the Kolm

It can be sort of unintuitive how the concept of computability necessarily involves infinity. For example: does there exist an algorithm that computes the Kolmogorov complexity, K(s), of string s for arbitrary s? It is well-known that the answer is "no" — there is no Turing machine that takes as input a string of arbitrary length and computes K(s). The proof is quite brief and involves the halting problem. But if we ask a similar question: does there exist an algorithm that computes K(s) of string s for arbitrary string s with length < n? The answer is yes! And there exists such an algorithm for any value of n. How is that possible? Think about it for a second, because the answer is going to disappoint you: simply create a Turing machine that consists of a giant lookup table for all 2^n possible strings that prints the value of K(s) for each one. But wait, that's cheating! Maybe so, but any specific implementation of the algorithm has a finite description. And by definition, K(s) is also finite for all s. While it's true that I haven't provided any particular method for determining the value of K(s) for all 2^n strings in order to actually create the lookup table, that doesn't matter. Such an algorithm nevertheless exists, regardless of whether you can find it or prove that it does what you want it to. So in a sense, finite questions about a finite number of things are sort of uninteresting from the perspective of computability, because you can always write a program that just prints the answer for all of those things (how quickly it does this is another matter). But when you extend the question to an infinite number of things, computability becomes much more interesting, because you don't know whether something finite can provide answers to questions about an infinite number of things.

SAI_Peregrinus 2y ago
There's also a simple algorithm to compute K(s) for any particular s (and thus for any finite set of such inputs). Enumerate every possible Turing machine by increasing length until one that outputs s is found. Since you've tried all shorter machines, and they didn't output s, you've found the shortest machine that outputs s and thus its length is K(s). Other machines of the same or greater length may exist which output s, but since K(s) is just about the minimal length this doesn't change anything. For all strings with length <n, you just repeat the brute-force for every one of the 2^n strings. It's a finite process!
- hyeoniuwu 2y ago
  This is incorrect. The problem is that you won't be able to tell if certain small Turing machines halt to give s, or loop forever. (So, if you are dovetailing through every possible Turing machine, the first one to output s may not be the minimal one. If you are not dovetailing, your search procedure will not halt, as you'll become stuck enumerating a Turing machine which does not halt.) (Besides, that there is an "algorithm to compute K(s) for any particular s" directly contradicts the non-computability of K(s).)
jmount 2y ago
Reminds me of the possible excess power of P/Poly versus P. Also does anybody remember the general name for circuit complexity classes where the circuit itself has to be written out by a simple Turing machine (I thought there was one but it isn't on the tip of my tong).
- bo1024 2y ago
  Yeah, the word is "uniform", e.g. a uniform family of circuits is one where there is a Turing machine where, for each n, it outputs the circuit for inputs of size n.
aidenn0 2y ago
Similar to how all real-world computers have a finite number of states and are thus not Turing machines, but rather finite state machines.
- forgot-im-old 2y ago
  Argh don't say that, someone might question funding CS theory grant proposals.
paulmd 2y ago
> But if we ask a similar question: does there exist an algorithm that computes K(s) of string s for arbitrary string s with length < n? The answer is yes! And there exists such an algorithm for any value of n. of course - n is by definition a finite number! and in fact at infinity, all finite numbers are quite small, actually. A mile might as well be a millimeter, from your chair at the end of the universe. And your scenario is basically just "hilbert's infinite hotel, on a computer" - we can of course add another program simply by moving all the existing programs 1 spot over... and it remains the exact same size of table needed to compute it! I would actually generalize this and just say that most people have poor intuition of how infinities (alephs, etc) and transfinite mathematics work in general. it's not a common subject, it's not a subject with everyday relevance, and it's deeply steeped in the emergent properties of mathematics and category/set theory. Like not only are infinities bigger than any finite number, but some infinities can nevertheless be bigger than other infinities etc - these are not things that are immediately obvious to the 3rd-grade concept of "infinity" that most people stop at. the much more interesting question would be if there exists an n < infinity such that the algorithm can be computed, and of course the answer is no (darn, there goes my turing prize).
ffhhj 2y ago
> a program that just prints the answer for all of those things Everything can be textualized, but making a complete interpreter for it requires understanding what intelligence really is.
gowld 2y ago
This description makes it sounds like large areas of computer science are just goofy, meaningless, games. But what's really happening is that "infinity" is standing in for "approximate, eventual, steady state behavior for sufficiently large N, larger than any specific one-off gimmick you might think of". In the real world, though, those gimmicks are important, and the constants and low-order terms ignored in a Big-O comparison are important to real world performance. There is constant tension between "big enough problem that the contant factors don't matter", and "small enough problem that it conforms to the (often implicit) of what 'constant' means (example: 32bit ints masquerading as integers)"
- cubefox 2y ago
  > This description makes it sounds like large areas of computer science are just goofy, meaningless, games. Well, only computability theory, not complexity theory, which you mention in the rest of your post.
- Xcelerate 2y ago
  > This description makes it sounds like large areas of computer science are just goofy, meaningless, games. Oh no, not at all. My point is that the concept of infinity is in a sense necessary for the mathematics involved in developing algorithms to solve problems. We are performing induction to "predict" the behavior of an infinite number of Turing machines without actually running them. We can't just iterate through all possible programs, so we have to use patterns that apply in a consistent way to all possible problem instances to narrow down the search space. > approximate, eventual, steady state behavior for sufficiently large N, larger than any specific one-off gimmick you might think of I know this is how computational complexity theory is considered from the perspective of many software engineers, but my point is a bit more fundamental. Computational complexity theory ultimately isn't concerned about any one particular problem and how to solve it quickly for practical applications—the goal is to understand what is and isn't possible with computation overall and with what resources (time, space). Why solve one problem when you can solve all of them? But to do that requires really understanding the mathematical structures behind computation itself. If you're a formalist, instead of thinking of infinity as "the limit of large n", you think of it as a concept in a formal system that involves manipulating symbols according to a set of axioms and inference rules. You can use whatever intuitive human-scale analogies you prefer when thinking about large cardinal axioms or the continuum hypothesis, but at the end of the day, all that matters in terms of computability and computational complexity is how exploring the space of proofs derivable from these formal systems leads to a better understanding about the behavior of Turing machines (and thus the nature and fundamental limits of computation).

SAI_Peregrinus 2y ago

There's also a simple algorithm to compute K(s) for any particular s (and thus for any finite set of such inputs). Enumerate every possible Turing machine by increasing length until one that outputs s is found. Since you've tried all shorter machines, and they didn't output s, you've found the shortest machine that outputs s and thus its length is K(s). Other machines of the same or greater length may exist which output s, but since K(s) is just about the minimal length this doesn't change anything. For all strings with length <n, you just repeat the brute-force for every one of the 2^n strings. It's a finite process!

hyeoniuwu 2y ago
This is incorrect. The problem is that you won't be able to tell if certain small Turing machines halt to give s, or loop forever. (So, if you are dovetailing through every possible Turing machine, the first one to output s may not be the minimal one. If you are not dovetailing, your search procedure will not halt, as you'll become stuck enumerating a Turing machine which does not halt.) (Besides, that there is an "algorithm to compute K(s) for any particular s" directly contradicts the non-computability of K(s).)

jmount 2y ago

Reminds me of the possible excess power of P/Poly versus P. Also does anybody remember the general name for circuit complexity classes where the circuit itself has to be written out by a simple Turing machine (I thought there was one but it isn't on the tip of my tong).

bo1024 2y ago
Yeah, the word is "uniform", e.g. a uniform family of circuits is one where there is a Turing machine where, for each n, it outputs the circuit for inputs of size n.

aidenn0 2y ago

Similar to how all real-world computers have a finite number of states and are thus not Turing machines, but rather finite state machines.

forgot-im-old 2y ago
Argh don't say that, someone might question funding CS theory grant proposals.

paulmd 2y ago

> But if we ask a similar question: does there exist an algorithm that computes K(s) of string s for arbitrary string s with length < n? The answer is yes! And there exists such an algorithm for any value of n. of course - n is by definition a finite number! and in fact at infinity, all finite numbers are quite small, actually. A mile might as well be a millimeter, from your chair at the end of the universe. And your scenario is basically just "hilbert's infinite hotel, on a computer" - we can of course add another program simply by moving all the existing programs 1 spot over... and it remains the exact same size of table needed to compute it! I would actually generalize this and just say that most people have poor intuition of how infinities (alephs, etc) and transfinite mathematics work in general. it's not a common subject, it's not a subject with everyday relevance, and it's deeply steeped in the emergent properties of mathematics and category/set theory. Like not only are infinities bigger than any finite number, but some infinities can nevertheless be bigger than other infinities etc - these are not things that are immediately obvious to the 3rd-grade concept of "infinity" that most people stop at. the much more interesting question would be if there exists an n < infinity such that the algorithm can be computed, and of course the answer is no (darn, there goes my turing prize).

ffhhj 2y ago

> a program that just prints the answer for all of those things Everything can be textualized, but making a complete interpreter for it requires understanding what intelligence really is.

gowld 2y ago

This description makes it sounds like large areas of computer science are just goofy, meaningless, games. But what's really happening is that "infinity" is standing in for "approximate, eventual, steady state behavior for sufficiently large N, larger than any specific one-off gimmick you might think of". In the real world, though, those gimmicks are important, and the constants and low-order terms ignored in a Big-O comparison are important to real world performance. There is constant tension between "big enough problem that the contant factors don't matter", and "small enough problem that it conforms to the (often implicit) of what 'constant' means (example: 32bit ints masquerading as integers)"

cubefox 2y ago
> This description makes it sounds like large areas of computer science are just goofy, meaningless, games. Well, only computability theory, not complexity theory, which you mention in the rest of your post.
Xcelerate 2y ago
> This description makes it sounds like large areas of computer science are just goofy, meaningless, games. Oh no, not at all. My point is that the concept of infinity is in a sense necessary for the mathematics involved in developing algorithms to solve problems. We are performing induction to "predict" the behavior of an infinite number of Turing machines without actually running them. We can't just iterate through all possible programs, so we have to use patterns that apply in a consistent way to all possible problem instances to narrow down the search space. > approximate, eventual, steady state behavior for sufficiently large N, larger than any specific one-off gimmick you might think of I know this is how computational complexity theory is considered from the perspective of many software engineers, but my point is a bit more fundamental. Computational complexity theory ultimately isn't concerned about any one particular problem and how to solve it quickly for practical applications—the goal is to understand what is and isn't possible with computation overall and with what resources (time, space). Why solve one problem when you can solve all of them? But to do that requires really understanding the mathematical structures behind computation itself. If you're a formalist, instead of thinking of infinity as "the limit of large n", you think of it as a concept in a formal system that involves manipulating symbols according to a set of axioms and inference rules. You can use whatever intuitive human-scale analogies you prefer when thinking about large cardinal axioms or the continuum hypothesis, but at the end of the day, all that matters in terms of computability and computational complexity is how exploring the space of proofs derivable from these formal systems leads to a better understanding about the behavior of Turing machines (and thus the nature and fundamental limits of computation).