3 ms·

What are practical consequences and examples of such in typical debates about politics, programming paradigms, etc?

by tabtab 7y ago

psychometry 7y ago
There aren't any. These theorems apply to specific systems in finitary number theory with certain axioms. They're important, but they're important in mathematical logic, not rhetoric or anything like that.
lacker 7y ago
One practical consequence is that the halting problem is undecidable, so if your boss asks you to build a program to check if another program will ever do X, you can tell them "hey that's an impossible task!"
- jmcqk6 7y ago
  In practical matters, this is not quite true. If you ask 'will this program launch a toaster to orbit mars', you can usually answer that question with high confidence. The halting problem describes the situations where you can't decide one way or another, but it does not say you can't decide anything. This is a very important distinction. We write code to analyze other code all the type. It's a core part of developer tools. If it was impossible, life would really suck.
triska 7y ago
Regarding programming paradigms, at least one very important consequence of the completeness theorem is that first-order logic can be used as a formal basis for computation. This is because you can model what a Turing machine does via predicates in first-order logic, describing a relation between states of the machine. The completeness theorem tells us that every semantic consequence of a first-order theory (with a well-orderable language) can be derived syntactically. This means that to derive results of the computation, we only have to systematically search for proofs. Due to the completeness theorem, we know that we won't miss anything (i.e., a result of the computation) that is actually the case. An immediate application is an important programming paradigm called logic programming. See for example Prolog, Mercury, and other languages that are based on this idea.

What are practical consequences and examples of such in typical debates about politics, programming paradigms, etc?

by tabtab 7y ago

What are practical consequences and examples of such in typical debates about politics, programming paradigms, etc?

There aren't any. These theorems apply to specific systems in finitary number theory with certain axioms. They're important, but they're important in mathematical logic, not rhetoric or anything like that.

lacker 7y ago

One practical consequence is that the halting problem is undecidable, so if your boss asks you to build a program to check if another program will ever do X, you can tell them "hey that's an impossible task!"

jmcqk6 7y ago
In practical matters, this is not quite true. If you ask 'will this program launch a toaster to orbit mars', you can usually answer that question with high confidence. The halting problem describes the situations where you can't decide one way or another, but it does not say you can't decide anything. This is a very important distinction. We write code to analyze other code all the type. It's a core part of developer tools. If it was impossible, life would really suck.

triska 7y ago

Regarding programming paradigms, at least one very important consequence of the completeness theorem is that first-order logic can be used as a formal basis for computation. This is because you can model what a Turing machine does via predicates in first-order logic, describing a relation between states of the machine. The completeness theorem tells us that every semantic consequence of a first-order theory (with a well-orderable language) can be derived syntactically. This means that to derive results of the computation, we only have to systematically search for proofs. Due to the completeness theorem, we know that we won't miss anything (i.e., a result of the computation) that is actually the case. An immediate application is an important programming paradigm called logic programming. See for example Prolog, Mercury, and other languages that are based on this idea.