3 ms·

The article claims, "Given that some sets of strings are decidable, it stands to reason that other sets of strings are not. " How can a string not be decidable

The article claims, "Given that some sets of strings are decidable, it stands to reason that other sets of strings are not. " How can a string not be decidable?! Just search for the string in the set. It is either there, or not there. What an I missing?

gus_massa 7y ago
You can have a infinite set of finite strings, for example {“1”, “11”, “111”, “1111”, “11111”, “111111”, “1111111”, “11111111”, ...}
- cellular 7y ago
  Is having an infinite amount of strings the only reason for the claim? Infinity breaks a lot of things. Infinity isn't even real. So I'm not sure this counts. It seems like the article would have mentioned infinity if that were the reason for the claim. It seems like Enumeration fails for an infinite set too.
  - Hercuros 7y ago
    Infinity is the only reason: all finite sets of strings are decidable, simply because you can just keep a list and see if a string is in there. Important to mention that there are decidable infinite sets of strings. For instance, deciding whether a string contains only ones is easy, even though there are infinitely many such strings and you couldn’t write all of them down. A lot of these ideas don’t require any actual “realized” infinity, however. For instance, there are infinitely many natural numbers, but natural numbers themselves are still finite. You can write a program that prints every number at some time in the nearby future (ignoring physical constraints), even though there is no point in time where it will have printed all numbers. If you want to take away infinity, you have to draw an arbitrary upper bound somewhere, since unbounded things are infinite. Drawing that line is fairly arbitrary since there is no reason why things should no longer work if you add just one more.
    - cellular 7y ago
      Did Godel say infinity is the reason too? Thanks for the response, I don't remember reading about infinity being the reason. Off topic: Still, you'd run out of matter in the universe (that you could use for ink), before you wrote down a finite amount of numbers while ever reaching a percentage of infinity. That's how unreal infinity is in my mind. I know the concept of infinity is useful in math, and in this incompleteness theorem, it seems like infinity is the very reason not all truths are provable. But I thought Godel's incompleteness theorem would apply to physical reality, but since infinity doesn't exist in physical reality, I'm not sure the incompleteness theorem would apply to physical reality. Hmmm Also, didn't Godel show his theorem to be informally true by stating, "This sentence is inprovably true."? There was no infinity invoked in that sentence.
      - Hercuros 7y ago
        Diagonalization arguments (which are used in Gödel's theorem) do require some infinity. If there were only a finite number of such "True, but unprovable using your current proof rules" sentences, then you could simply add those sentences to your list of proof rules and there would be nothing "True, but unprovable" anymore. For Gödel's theorem to work, you need at least an infinite supply of those kinds of sentences. Also here there's no need to actually write down all of them exhaustively. It's just important to be able to find "yet another one" whenever you would like to, which requires an inexhaustible supply.
        cellular 7y ago
        "which requires an inexhaustible supply. " But this is how you can stress the theorem. I know it will take a long time, so consider a universe where only 1000 bits of matter actually exist, then try to use the theorem and you won't have enough ink to even hold the theorem, and sets in memory. It's the same for our universe, just with more bits. "you could simply add those sentences to your list of proof rules " Thanks, for responding. Do you mean axioms? I don't understand why that would be a solution. I'll have to read Godel again.

gus_massa 7y ago

You can have a infinite set of finite strings, for example {“1”, “11”, “111”, “1111”, “11111”, “111111”, “1111111”, “11111111”, ...}

cellular 7y ago
Is having an infinite amount of strings the only reason for the claim? Infinity breaks a lot of things. Infinity isn't even real. So I'm not sure this counts. It seems like the article would have mentioned infinity if that were the reason for the claim. It seems like Enumeration fails for an infinite set too.
- Hercuros 7y ago
  Infinity is the only reason: all finite sets of strings are decidable, simply because you can just keep a list and see if a string is in there. Important to mention that there are decidable infinite sets of strings. For instance, deciding whether a string contains only ones is easy, even though there are infinitely many such strings and you couldn’t write all of them down. A lot of these ideas don’t require any actual “realized” infinity, however. For instance, there are infinitely many natural numbers, but natural numbers themselves are still finite. You can write a program that prints every number at some time in the nearby future (ignoring physical constraints), even though there is no point in time where it will have printed all numbers. If you want to take away infinity, you have to draw an arbitrary upper bound somewhere, since unbounded things are infinite. Drawing that line is fairly arbitrary since there is no reason why things should no longer work if you add just one more.
  - cellular 7y ago
    Did Godel say infinity is the reason too? Thanks for the response, I don't remember reading about infinity being the reason. Off topic: Still, you'd run out of matter in the universe (that you could use for ink), before you wrote down a finite amount of numbers while ever reaching a percentage of infinity. That's how unreal infinity is in my mind. I know the concept of infinity is useful in math, and in this incompleteness theorem, it seems like infinity is the very reason not all truths are provable. But I thought Godel's incompleteness theorem would apply to physical reality, but since infinity doesn't exist in physical reality, I'm not sure the incompleteness theorem would apply to physical reality. Hmmm Also, didn't Godel show his theorem to be informally true by stating, "This sentence is inprovably true."? There was no infinity invoked in that sentence.
    - Hercuros 7y ago
      Diagonalization arguments (which are used in Gödel's theorem) do require some infinity. If there were only a finite number of such "True, but unprovable using your current proof rules" sentences, then you could simply add those sentences to your list of proof rules and there would be nothing "True, but unprovable" anymore. For Gödel's theorem to work, you need at least an infinite supply of those kinds of sentences. Also here there's no need to actually write down all of them exhaustively. It's just important to be able to find "yet another one" whenever you would like to, which requires an inexhaustible supply.
      - cellular 7y ago
        "which requires an inexhaustible supply. " But this is how you can stress the theorem. I know it will take a long time, so consider a universe where only 1000 bits of matter actually exist, then try to use the theorem and you won't have enough ink to even hold the theorem, and sets in memory. It's the same for our universe, just with more bits. "you could simply add those sentences to your list of proof rules " Thanks, for responding. Do you mean axioms? I don't understand why that would be a solution. I'll have to read Godel again.