5 ms·

Seems like a problem for philosophy of language... When we say "it cannot find the best pattern", what does this mean? 1. We assume "the best pattern" exists.

Seems like a problem for philosophy of language... When we say "it cannot find the best pattern", what does this mean? 1. We assume "the best pattern" exists. But what do we mean here by "exists"? If something is uncomputable does it exist? In what sense?

arketyp 8y ago
The Gödel sentence is uncomputable but is commonly held to be true. A non-constructivst would probably be more inclined to say that something which is uncomputable can exist. But it is not obvious (to me). Noteworthy is that Per Martin-Löf who is also credited for the accepted definition of algorithmic randomness for infinite sequences, based on Kolmogorov complexity, developed inuitionistic type theory, a framework for the foundation of mathematics in the constructivist school.
- mikorym 8y ago
  What is Martin-Löf's definition of algorithmic randomness (for infinite sequences)?
  - arketyp 8y ago
    I'm not competent enough to attempt my own explanation. The Wikipedia articles are good: https://en.wikipedia.org/wiki/Algorithmically_random_sequence https://en.wikipedia.org/wiki/Algorithmically_random_sequenc...
FartyMcFarter 8y ago
The halting problem is uncomputable too, but any given Turing machine either halts or never halts (even if we don't have a general procedure for determining which). There is no third choice. Similarly, there is definitely a shortest program that outputs a certain string and then halts. We can't always make a program to find it, but that shortest program exists nonetheless. There is no other choice! If there is no shortest program to output it, how can there be any other program?
foldr 8y ago
There's no linguistic problem, assuming that (i) definite descriptions are quantificational and (ii) the relevant quantifier can scope under negation. "It cannot find the best pattern" means "It is not the case that it can find a pattern x such that no other pattern y is better than x".
kannanvijayan 8y ago
I thought about it a while back when it came up in my studies, and in this case I think it's easy to make the argument that it exists (some shortest program+input P+I that produces a given finite-length string S), but not computable. Programs + Input in the K-complexity world are sequences of symbols taken from a finite alphabet. For any finite-length S, we can definitely find a program Q that produces S: Simply write the program that literally embeds and reproduces S. Now, Q is a program+input that has finite length. So we can always find a maximal bound for the K-complexity (length of Q). Since Q is a finite-length symbol sequence from a finite alphabet, we can consider the finite-sized subset of all symbol-sequences of length <= Q. Every single one of those sequences describes a program + input. Every one of those programs is deterministic: it will either run to completion and produce some fixed output, or never-terminate. We know the finite upper bound exists. We know the finite set of Program+Input sequences exist. We can even enumerate all of them (and write a program to do it). We also know that each of them will deterministically either produce S or not produce S (we can't be guaranteed that we will run them all and find the results of each, but we know each of them have an intrinsic and deterministic behaviour). Either one or more of those will produce S or not. If there are none, then our candidate Q is the shortest. If there are one or more, then the shortest of those definitely exists, since we already have the finite set it comes from in our hand. Overall, this and other cases (Godel's work, Halting Problem) lead me down the path of accepting the mathematical truth that it's possible for there to be truths we never "reach". Truth and knowability are linked, but knowability is not a prerequisite for truth. It wasn't an easy idea to come to terms with, but I'm relatively comfortable with it these days.
hcs 8y ago
Something(X) exists for a given X. Another something to compute Something(X) for any given X does not.

arketyp 8y ago

The Gödel sentence is uncomputable but is commonly held to be true. A non-constructivst would probably be more inclined to say that something which is uncomputable can exist. But it is not obvious (to me). Noteworthy is that Per Martin-Löf who is also credited for the accepted definition of algorithmic randomness for infinite sequences, based on Kolmogorov complexity, developed inuitionistic type theory, a framework for the foundation of mathematics in the constructivist school.

mikorym 8y ago
What is Martin-Löf's definition of algorithmic randomness (for infinite sequences)?
- arketyp 8y ago
  I'm not competent enough to attempt my own explanation. The Wikipedia articles are good: https://en.wikipedia.org/wiki/Algorithmically_random_sequence https://en.wikipedia.org/wiki/Algorithmically_random_sequenc...

FartyMcFarter 8y ago

The halting problem is uncomputable too, but any given Turing machine either halts or never halts (even if we don't have a general procedure for determining which). There is no third choice. Similarly, there is definitely a shortest program that outputs a certain string and then halts. We can't always make a program to find it, but that shortest program exists nonetheless. There is no other choice! If there is no shortest program to output it, how can there be any other program?

foldr 8y ago

There's no linguistic problem, assuming that (i) definite descriptions are quantificational and (ii) the relevant quantifier can scope under negation. "It cannot find the best pattern" means "It is not the case that it can find a pattern x such that no other pattern y is better than x".

kannanvijayan 8y ago

I thought about it a while back when it came up in my studies, and in this case I think it's easy to make the argument that it exists (some shortest program+input P+I that produces a given finite-length string S), but not computable. Programs + Input in the K-complexity world are sequences of symbols taken from a finite alphabet. For any finite-length S, we can definitely find a program Q that produces S: Simply write the program that literally embeds and reproduces S. Now, Q is a program+input that has finite length. So we can always find a maximal bound for the K-complexity (length of Q). Since Q is a finite-length symbol sequence from a finite alphabet, we can consider the finite-sized subset of all symbol-sequences of length <= Q. Every single one of those sequences describes a program + input. Every one of those programs is deterministic: it will either run to completion and produce some fixed output, or never-terminate. We know the finite upper bound exists. We know the finite set of Program+Input sequences exist. We can even enumerate all of them (and write a program to do it). We also know that each of them will deterministically either produce S or not produce S (we can't be guaranteed that we will run them all and find the results of each, but we know each of them have an intrinsic and deterministic behaviour). Either one or more of those will produce S or not. If there are none, then our candidate Q is the shortest. If there are one or more, then the shortest of those definitely exists, since we already have the finite set it comes from in our hand. Overall, this and other cases (Godel's work, Halting Problem) lead me down the path of accepting the mathematical truth that it's possible for there to be truths we never "reach". Truth and knowability are linked, but knowability is not a prerequisite for truth. It wasn't an easy idea to come to terms with, but I'm relatively comfortable with it these days.

hcs 8y ago

Something(X) exists for a given X. Another something to compute Something(X) for any given X does not.