Re:Unprovability comes to machine learning
by antidesitter on Thursday January 10, 2019 @02:46AM
(#18872229)
> Where it's difficult is when we talk about numbers that aren't describable in a finite number of terms, i.e. Uncomputable.
I might be nitpicking here, but uncomputable != indescribable. For example, Chaitin’s constant [1] is uncomputable but perfectly describable (and in fact limit-computable [2]). The set of arithmetically-definable [3] numbers is even larger than that of limit-computable numbers. Computable and limit-computable numbers lie at levels Δ^0_1 and Δ^0_2 of this hierarchy, respectively.
I might be nitpicking here, but uncomputable != indescribable. For example, Chaitin’s constant [1] is uncomputable but perfectly describable (and in fact limit-computable [2]). The set of arithmetically-definable [3] numbers is even larger than that of limit-computable numbers. Computable and limit-computable numbers lie at levels Δ^0_1 and Δ^0_2 of this hierarchy, respectively.
[1] https://en.wikipedia.org/wiki/Chaitin%27s_constant
[2] https://en.wikipedia.org/wiki/Computation_in_the_limit
[3] https://en.wikipedia.org/wiki/Arithmetical_set