\r\nThis was written January 14th, 2026<\/i>\r\n<\/p>\r\n\r\nUndecidability Rant<\/h2>\r\n
\r\nThe Halting Problem<\/a> is a very common one people get exposed to when studying\r\ncomputer science. It demonstrates a new concept, undecidability<\/i>, and what a concept for\r\nnew students! You’re telling me you have a problem that does have a solution, and yet there’s\r\nno actual algorithm to solve this? But…how? That’s wild!\r\n<\/p> \r\nBut as a student with a background in Mathematics, I was always bothered by this problem\r\nand why we cared so much about Undecidablity<\/a> (beyond the hand-wavy explanation I received\r\nat the time). And after all this time, I’m clearer on why it annoys me. It’s because\r\nit’s not so much a matter of “Can this be solved?”, it’s a matter of “Are we trying to\r\nsolve something infinite within a finite amount of steps?”. And we tend to just use flourish\r\nand hide away this part.\r\n<\/p> \r\nHonestly, this should have been clear to me the first time undecideability of a problem\r\nwas finally proven to me rigorously. We used a trick very similar to how we usually prove\r\nuncountability of the real numbers.\r\n<\/p> \r\nSimilarly, here’s an extremely simple example a friend once presented to me: knowing\r\nwhether an arbitrary number in decimal form is rational or not…is undecidable.\r\nWell, of course it is, a computer could never identify an irrational number as being so.\r\nAny step could potentially be the last one, and we cannot reach infinity. \r\n<\/p> \r\nSo, to get back to the the core, why does this bug me? Because we show present this\r\nas a grandiose class of mythical problems, one that you can’t build an algorithm for,\r\nbut it’s because they’re dealing with unrealistic domains. And then simply opt to not\r\ncare about potential solutions.\r\n<\/p> \r\nLet me clarify. Suppose you limited the Halting Problem to be over a Turing Machine\r\nwith a finite tape (a Linear bounded automaton<\/a>), then it’s pretty clear to see\r\nthat it is<\/i> decidable. After all, there’s now only a finite (albeit astronomical) number\r\nof states such a tape could have. Accordingly, any program will either end, or reach a\r\nstate it has already reached before, thereafter being stuck in a loop. We could thus use\r\na simple brute-force algorithm to solve this bound Halting Problem. (Do\r\nnote that we may<\/i> need a bigger machine to make those calculations.)\r\n<\/p> \r\nAnd yet, students are usually not presented with this consideration. Instead, a more\r\ncommon scenario is: “Oh yeah, there’s this thing you can’t solve. And if you want to\r\nshow something else is undecidable, you reduce it to the Halting Problem.”.\r\n<\/p> \r\nBut, considering this problem is in an impractical domain…that seems short-sighted to\r\nme, we’re giving up too quickly. Why not attempt to solve these problems within a more\r\ninteresting sub-domain? This is done all the time in theoretical Mathematics, choosing\r\ndifferent domains and studying their properties.\r\n<\/p> \r\nIn my opinion, this would be much more interesting. Let’s use a bounded version of\r\nthese problems, where we look at arbitrarily large finite sets (which are more practical)\r\nand seeing whether we can find any clever solutions. And if so, what sort of Time\r\nComplexity \r\nWell, that was my rant about Undecidabililty. Thanks for listening, and remember to stay\r\ncurious!\r\n<\/p> \r\nP.S.: At some point, I was wondering whether this was really about uncountability vs\r\ncountability instead, until I convinced myself that we can still get undecidability while\r\nlimiting ourselves to a countable set. Simply do the “rational vs irrational” bit, but\r\nlimit your irrational numbers to a countable set, let’s say multiples of Pi, and this\r\nshould still be undecidable.\r\n<\/p>\r\n","protected":false},"excerpt":{"rendered":" This was written January 14th, 2026 Undecidability Rant The Halting Problem is a very common one people get exposed to when studying computer science. It demonstrates a new concept, undecidability, and what a concept for new students! You’re telling me you have a problem that does have a solution, and yet there’s no actual algorithm … Continue reading Blog Post: Undecidability Rant<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"bgseo_title":"","bgseo_description":"","bgseo_robots_index":"index","bgseo_robots_follow":"follow","footnotes":""},"categories":[1],"tags":[],"class_list":["post-2696","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.shawnmeanders.com\/blog\/wp-json\/wp\/v2\/posts\/2696","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shawnmeanders.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shawnmeanders.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shawnmeanders.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shawnmeanders.com\/blog\/wp-json\/wp\/v2\/comments?post=2696"}],"version-history":[{"count":1,"href":"https:\/\/www.shawnmeanders.com\/blog\/wp-json\/wp\/v2\/posts\/2696\/revisions"}],"predecessor-version":[{"id":2697,"href":"https:\/\/www.shawnmeanders.com\/blog\/wp-json\/wp\/v2\/posts\/2696\/revisions\/2697"}],"wp:attachment":[{"href":"https:\/\/www.shawnmeanders.com\/blog\/wp-json\/wp\/v2\/media?parent=2696"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shawnmeanders.com\/blog\/wp-json\/wp\/v2\/categories?post=2696"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shawnmeanders.com\/blog\/wp-json\/wp\/v2\/tags?post=2696"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}