Computably enumerable sets and undecidability
Channel: Nikolaj-K
Date: 2019-08-11

In this video we're going to define and implement decidable as well as semidecidable. Code is found under https://gist.github.com/Nikolaj-K/808149debf7c3b09705127f9205f6c3f Other names for the two are recursive or computable resp. recursively enumerable, computably enumerable - I also say computationally enumerable in the video. We implement generic dovetailing of state machines and use it to sketch the undecidability of the halting problems. Notions such as total functions are touched upon and facts about computable functions are motivated. The unsolved Collatz conjecture is used as a main example.

https://en.wikipedia.org/wiki/Recursively_enumerable_set
https://en.wikipedia.org/wiki/Halting_problem
https://en.wikipedia.org/wiki/Collatz_conjecture
https://en.wikipedia.org/wiki/Dovetailing_(computer_science)