Undecidable Languages - Easy Theory

Currently Playing: How accurate is Veritasium about the Collatz 3x+1 Problem?

Easy Theory Website: https://www.easytheory.org GoFundMe: https://www.gofundme.com/f/easy-theory-video-studio Patreon: https://www.patreon.com/EasyTheoryYT Fourthwall: https://easy-theory-llc-shop.fourthwall.com Problem Solving channel: ​⁠ @easytheoryprobsolve We correct a minor point on Veritasium's video about the Collatz Conjecture (aka the 3x+1 problem) in that he claimed it may be undecidable. The issue is that, in some "reasonable" descriptions of the problem, it *is* decidable; just that we may not now what the decider actually is! But in others, it may or may not be decidable. In fact, we give some sufficient assumptions for the 3x+1 problem to be true, which are somewhat reasonable to make based on previous work. (We love Veritasium here! ❤️) What is the 3x+1 problem? Take any positive integer x, and apply the following operation: if x is even, divide it by 2; and if it is odd, multiply it by 3 and add 1. The trajectory of x then is the sequence of numbers x, f(x), f(f(x)), etc., where f is the operation. The conjecture claims that every integer x larger than 1 contains 1 in the trajectory of x. What are the roadblocks to proving the 3x+1 conjecture? There are three possible behaviors of any trajectory: (1) it contains 1, (2) it contains a repeated value, other than 1--4--2--1--..., or (3) it tends towards infinity. The issue is that one needs to say something about the prime factorizations of the numbers 3x and 3x+1, but these can be wildly different. Think about any power of 2, and one less than it; there is no prime factor in common between them. Yet the conjecture is equivalent to "landing" on a power of 2 eventually (since that eventually yields 1 always). Another equivalent form of the conjecture is: every positive integer x eventually contains some number less than x in its trajectory exactly once, other than 1, 2, and 4. I show the following results: (1) Consider the following problem formulation: given a positive integer x, every integer larger than x contains 1 in its trajectory. Then this problem may or may not be decidable (which is an open research question). (2) Even if we assume (1) is decidable, the entire conjecture STILL may or may not be decidable. (3) If the conjecture is formulated as: construct a language L such that L = {1} if the 3x+1 conjecture is true, and L = {0} otherwise, then unconditionally L is decidable. (4) If the following assumption is made: there exists an n0 such that every number x larger than n0 contains 1 in its trajectory, then the 3x+1 problem is decidable (and further, any counterexample involves a cycle, and not tending towards infinity). It's important we understand the technical terms so that we can be accurate in communicating technical topics like this one. I also give the example of Turing Machines and Linear Bounded Automata to show that just because a "larger" class of problems is undecidable, does not imply the "smaller" class is undecidable. All of the rest of the video is great, please check it out; just this one item needed correcting. Veritasium's video: https://www.youtube.com/watch?v=094y1Z2wpJg&ab_channel=Veritasium Reddit thread: https://www.reddit.com/r/math/comments/oumc19/the_simplest_math_problem_no_one_can_solve/ Timeline: 0:00 - Intro 0:08 - Part of Veritasium's Video 0:50 - Beginning of my Rant 2:12 - One Encoding of the 3x+1 Problem 6:30 - Why Generalized Problem does not imply Specific problem behavior 10:25 - A Decidable Encoding of the 3x+1 Problem 15:40 - How a (reasonable, possible) assumption can show Decidability 23:16 - Recap If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1