🧵 Untitled Thread
Anonymous at Sat, 16 Mar 2024 19:55:42 UTC 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 at Sat, 16 Mar 2024 20:14:29 UTC 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 at Sat, 16 Mar 2024 20:37:18 UTC No. 16081859
>>16081805
computably enumerable = semidecidable
computable = decidable
Obviously the former is more general than the latter.