9 ms·

Computing the Uncomputable

78 points by mathgenius 11y ago

mchahn 11y ago
My favorite sentence ... "I used to think that I knew what I had always thought it to mean, but I no longer think so".
- asQuirreL 11y ago
  Any day in which you can say this, is a good day.
  - Joof 11y ago
    I live for these days. I don't get many of them anymore which is a shame.
daralthus 11y ago
This: Perhaps it is fair to say that “finite” does not mean what we have always thought it to mean. What have we always thought it to mean? I used to think that I knew what I had always thought it to mean, but I no longer think so. If we go down this road, Hamkins’ result takes on a different significance. It says that any subjectivity in the notion of ‘natural number’ may also infect what it means for a Turing machine to halt, and what function a Turing machine computes when it does halt. Is beautiful. It seems like another proof for a leaky abstraction and incomepleteness. We have to forget finite or admit that it has bounds on what we can explore with it, as it already defines our model.
ikeboy 11y ago
1. I'm studying set theory, and finite is quite rigidly defined (albeit there's multiple definitions, which require the axiom of choice to prove identical.) We can define natural number as an ordinal that's well ordered by its element relation and the reverse of the element relation (all those terms are defined). Or just as a finite ordinal, in the sense of not being equipollent to any strict subset. Or as the ordinals not containing any limit ordinals or being a limit ordinal. 2. This should probably be thought of as the machine doesn't halt, but in some models, we can "prove" that it halts and has any result. This is kind of like how you can rearrange the terms of some series to sum to any number. https://en.wikipedia.org/wiki/Riemann_series_theorem https://en.wikipedia.org/wiki/Riemann_series_theorem (I wonder if there's a way to get the computability result from this result by some clever isomorphism.) Edit: fixed definition and added another one.
- cousin_it 11y ago
  > finite is quite rigidly defined It's a bit more subtle. Wikipedia puts it well: Even for those mathematicians who embrace infinite sets, in certain important contexts, the formal distinction between the finite and the infinite can remain a delicate matter. The difficulty stems from Gödel's incompleteness theorems. One can interpret the theory of hereditarily finite sets within Peano arithmetic (and certainly also vice versa), so the incompleteness of the theory of Peano arithmetic implies that of the theory of hereditarily finite sets. In particular, there exists a plethora of so-called non-standard models of both theories. A seeming paradox, non-standard models of the theory of hereditarily finite sets contain infinite sets - but these infinite sets look finite from within the model. (This can happen when the model lacks the sets or functions necessary to witness the infinitude of these sets.) On account of the incompleteness theorems, no first-order predicate, nor even any recursive scheme of first-order predicates, can characterize the standard part of all such models. So, at least from the point of view of first-order logic, one can only hope to characterize finiteness approximately. https://en.wikipedia.org/wiki/Finite_set https://en.wikipedia.org/wiki/Finite_set
  - ikeboy 11y ago
    Can you have a model of ZF with natural numbers that aren't just 0,1,2,...? Or only PA? It seemed obvious that defining the natural numbers in the way above results in only such numbers. You can give an intuitive argument that any natural number can be recursively generated from 0 by the successor operator. Is this wrong? Edit: looks like http://www1.cuni.cz/~svejdar/papers/sv_ybk10_p.pdf http://www1.cuni.cz/~svejdar/papers/sv_ybk10_p.pdf says you can get such a model. >A model M of (some) set theory is non-standard if it contains an ordinal α such that M |= “α is finite”, i.e. M |= “α is less than the first limit ordinal”, but looking from outside, the set of all ordinals β < α is infinite. The proof of the existence of non-standard models of set theory is basically the same as for PA.
    - cousin_it 11y ago
      Yes, all theories at least as strong as PA (including ZF) have models with nonstandard naturals. Another fun fact is that ZF has a countable model, even though ZF proves that uncountable sets exist. https://en.wikipedia.org/wiki/Skolem%27s_paradox https://en.wikipedia.org/wiki/Skolem%27s_paradox
luckystarr 11y ago
Rosser's trick seems nice. Kind of reminds me of tail-call optimization.
jpfed 11y ago
Am I thinking of this correctly? In PA, you start with zero and a successor function, such that > is transitive and succ(a) > a. In nonstandard models, you start with a successor function and zero, but also at least one other weird entity not reachable by any number of applications of the successor function to zero. You can apply the successor function to that entity to get new numbers that are all greater than anything reachable from zero. OR is it that there have to be infinite starting objects? OR should we think of it as having zero and both a successor function and a weirdSuccessor function (whose applications commute) such that > considers the number of weirdSuccessor applications before it looks at the number of successor applications?
- tamana 11y ago
  It means that you have 0, and you have Big, and Big is axiomatically larger than all iterated successors of 0. And Big has iterated successors as well. For example, consider the set embedded in the rationals as 0, 1/2, 3/4, 7/8 , ... , 1, 3/2, 7/4, 15/8, ...

78 points by mathgenius 11y ago

mchahn 11y ago

My favorite sentence ... "I used to think that I knew what I had always thought it to mean, but I no longer think so".

asQuirreL 11y ago
Any day in which you can say this, is a good day.
- Joof 11y ago
  I live for these days. I don't get many of them anymore which is a shame.

daralthus 11y ago

This: Perhaps it is fair to say that “finite” does not mean what we have always thought it to mean. What have we always thought it to mean? I used to think that I knew what I had always thought it to mean, but I no longer think so. If we go down this road, Hamkins’ result takes on a different significance. It says that any subjectivity in the notion of ‘natural number’ may also infect what it means for a Turing machine to halt, and what function a Turing machine computes when it does halt. Is beautiful. It seems like another proof for a leaky abstraction and incomepleteness. We have to forget finite or admit that it has bounds on what we can explore with it, as it already defines our model.

ikeboy 11y ago

1. I'm studying set theory, and finite is quite rigidly defined (albeit there's multiple definitions, which require the axiom of choice to prove identical.) We can define natural number as an ordinal that's well ordered by its element relation and the reverse of the element relation (all those terms are defined). Or just as a finite ordinal, in the sense of not being equipollent to any strict subset. Or as the ordinals not containing any limit ordinals or being a limit ordinal. 2. This should probably be thought of as the machine doesn't halt, but in some models, we can "prove" that it halts and has any result. This is kind of like how you can rearrange the terms of some series to sum to any number. https://en.wikipedia.org/wiki/Riemann_series_theorem https://en.wikipedia.org/wiki/Riemann_series_theorem (I wonder if there's a way to get the computability result from this result by some clever isomorphism.) Edit: fixed definition and added another one.

cousin_it 11y ago
> finite is quite rigidly defined It's a bit more subtle. Wikipedia puts it well: Even for those mathematicians who embrace infinite sets, in certain important contexts, the formal distinction between the finite and the infinite can remain a delicate matter. The difficulty stems from Gödel's incompleteness theorems. One can interpret the theory of hereditarily finite sets within Peano arithmetic (and certainly also vice versa), so the incompleteness of the theory of Peano arithmetic implies that of the theory of hereditarily finite sets. In particular, there exists a plethora of so-called non-standard models of both theories. A seeming paradox, non-standard models of the theory of hereditarily finite sets contain infinite sets - but these infinite sets look finite from within the model. (This can happen when the model lacks the sets or functions necessary to witness the infinitude of these sets.) On account of the incompleteness theorems, no first-order predicate, nor even any recursive scheme of first-order predicates, can characterize the standard part of all such models. So, at least from the point of view of first-order logic, one can only hope to characterize finiteness approximately. https://en.wikipedia.org/wiki/Finite_set https://en.wikipedia.org/wiki/Finite_set
- ikeboy 11y ago
  Can you have a model of ZF with natural numbers that aren't just 0,1,2,...? Or only PA? It seemed obvious that defining the natural numbers in the way above results in only such numbers. You can give an intuitive argument that any natural number can be recursively generated from 0 by the successor operator. Is this wrong? Edit: looks like http://www1.cuni.cz/~svejdar/papers/sv_ybk10_p.pdf http://www1.cuni.cz/~svejdar/papers/sv_ybk10_p.pdf says you can get such a model. >A model M of (some) set theory is non-standard if it contains an ordinal α such that M |= “α is finite”, i.e. M |= “α is less than the first limit ordinal”, but looking from outside, the set of all ordinals β < α is infinite. The proof of the existence of non-standard models of set theory is basically the same as for PA.
  - cousin_it 11y ago
    Yes, all theories at least as strong as PA (including ZF) have models with nonstandard naturals. Another fun fact is that ZF has a countable model, even though ZF proves that uncountable sets exist. https://en.wikipedia.org/wiki/Skolem%27s_paradox https://en.wikipedia.org/wiki/Skolem%27s_paradox

luckystarr 11y ago

Rosser's trick seems nice. Kind of reminds me of tail-call optimization.

jpfed 11y ago

Am I thinking of this correctly? In PA, you start with zero and a successor function, such that > is transitive and succ(a) > a. In nonstandard models, you start with a successor function and zero, but also at least one other weird entity not reachable by any number of applications of the successor function to zero. You can apply the successor function to that entity to get new numbers that are all greater than anything reachable from zero. OR is it that there have to be infinite starting objects? OR should we think of it as having zero and both a successor function and a weirdSuccessor function (whose applications commute) such that > considers the number of weirdSuccessor applications before it looks at the number of successor applications?

tamana 11y ago
It means that you have 0, and you have Big, and Big is axiomatically larger than all iterated successors of 0. And Big has iterated successors as well. For example, consider the set embedded in the rationals as 0, 1/2, 3/4, 7/8 , ... , 1, 3/2, 7/4, 15/8, ...