New answers tagged

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