top | item 33270432

(no title)

ghancock | 3 years ago

knaekhoved your comment is dead which I think is unfortunate because it seems better to inform you than bury your comment so I'll reply here: the page did mean N -> N, given the context of the previous paragraph. You may have thought what you did if you did not know that Card(N)^Card(N) is equal to 2^Card(N) by the laws of arithmetic for cardinal numbers. If you have not encountered those before there are enough on Wikipedia to show that equality https://en.wikipedia.org/wiki/Cardinal_number#Cardinal_arith....

discuss

order

rocqua|3 years ago

Besides the equivalence, computable functions are about more than just decision problems. Computable functions are a subset of N -> N. I suppose the confusion is that undecidability (very similar to uncomputability) regards decision problems of the form N -> Bool. This class of functions is also what P vs NP, and general complexity theory tends to focus on.

But the question "is this function computable" is sensible to ask for any function N -> N.