New answers tagged logic
2
As cody observed, the problem with that strategy is that definable relations need not be computable. For example, the Halting Problem is definable in $(\mathbb{N}; +,\times)$ (see Kleene's $T$-predicate).
That said, a relativized form of the incomputability of the Halting Problem, applied to iterates of the Turing jump, does do the job:
First, we show that ...
1
I'm not sure how to simplify this equation from the point you've gotten to without backtracking (e.g., recognizing that AB implies ABC' + ABC). The way I would do it is, starting from the beginning:
D = ABC + AB’C + A’B’C + ABC’ + A’BC’ + AB’C’
If we rearrange this as follows:
D = ABC + ABC’ + AB’C + AB’C’ + A’B’C + A’BC’
Then you may notice that we have:...
Top 50 recent answers are included
