3 ms·
Any Turing-complete programming language can be reduced to any other Turing-complete programming language. A "reduction" is just an implementation. And we don
by zozbot234 4y ago
Any Turing-complete programming language can be reduced to any other Turing-complete programming language. A "reduction" is just an implementation. And we don't care about how efficient the reduction is, only that it exist. Efficiency enters afterwards as a separate concern.
- layer8 4y agoNot sure what point you’re making. My concern has nothing to do with efficiency, and the fact of Turing equivalence is exactly part of my point: There doesn’t seem to be an analogous common underlying model like Turing equivalence for the mathematical foundations.
- zozbot234 4y agoOf course there is; that's what the slide deck ends up discussing at length. What one might say is that there's not a single underlying model; the logical expressiveness of Peano Arithmetic is not the same as ZF set theory, or ZFC which adds choice to ZF. But even in CS we care about sub-Turing computational models.
- layer8 4y agoYeah, but that lack of a single underlying model is why I don’t agree about the analogy. There is no disagreement about what “computation” means or of what is computationally possible, because we have a single model for that (and the Church–Turing thesis). And that single model is what constitutes the foundation, not the programming languages — which however are presented as foundations in the analogy made in the slides. In comparison, the situation is much less clear-cut and unanimous for the foundations of mathematics.
- wannabebarista 4y agoThis is a fair point. The analogy in the slides doesn't say anything about the veracity of mathematical propositions. While the notion of computable is mostly agreed on, it's unclear, for instance, if we should be doing mathematics in a world where the continuum hypothesis is true, false, or independent of our theory. With that said, one can still adopt the programming language analogy for particular models that the various foundations capture. So you don't have to solve the multiverse problem to use the analogy.[0] [0] https://en.m.wikipedia.org/wiki/Multiverse_(set_theory) https://en.m.wikipedia.org/wiki/Multiverse_(set_theory)
- naasking 4y ago> Yeah, but that lack of a single underlying model is why I don’t agree about the analogy. There is no single underlying model for mathematics either. This is a consequence of Godel incompleteness. It holds for both programming languages and math because they're all formal systems, just with different properties.