/sci/ - Science & Math

[Anonymous No.16081805]

>The domain of any universal computable function is a computably enumerable set but never a computable set.

how the fuck can it be enumerable but not computable?

[Anonymous No.16081831]

>>16081805
The Collatz conjecture is not proven, i.e. we don't know that for each number n, if you run the algorithm c it won't run away to infinity.
Framed in terms of sets, we define the set C:={n in N | c(n)=1} and it's not known whether C=N.

By dovetailing, we can enumerate all elements of C:
* Do the first computational step to evaluate c(0)
* Do the second computational step to evaluate c(0) and the first for c(1)
* Do the third computational step to evaluate c(0), the second for c(1) and the first for c(2)
* Etc.
All m for which c(m)=1 will eventually fall out. We can enumerate all elements of C.

Nonetheless, it might be that we can't device if c halts or not for all inputs.

Popping out all elements for which the thing terminates is thus apirori easier than deciding for each m whether it's in C.

[Anonymous No.16081836]

Equipped with this example, read again

https://en.wikipedia.org/wiki/Computable_set

[Anonymous No.16081859]

>>16081805
computably enumerable = semidecidable
computable = decidable

Obviously the former is more general than the latter.