CS101++ - What Are Computability and the Halting Problem?

☟☟ Awesome T-Shirts! Sponsors! Books! ☟☟
Upcoming Workshop: Understanding Object Lifetime, C++ On Sea, July 2, 2024
► cpponsea.uk/2024/sessions/und...
Upcoming Workshop: C++ Best Practices, NDC TechTown, Sept 9-10, 2024
► ndctechtown.com/workshops/c-b...
github.com/lefticus/cpp_weekl... for open ended conversions about CS101++ videos
T-SHIRTS AVAILABLE!
► The best C++ T-Shirts anywhere! my-store-d16a2f.creator-sprin...
WANT MORE JASON?
► My Training Classes: emptycrate.com/training.html
► Follow me on twitter: / lefticus
SUPPORT THE CHANNEL
► Patreon: / lefticus
► Github Sponsors: github.com/sponsors/lefticus
► Paypal Donation: www.paypal.com/donate/?hosted...
GET INVOLVED
► Video Idea List: github.com/lefticus/cpp_weekl...
JASON'S BOOKS
► C++23 Best Practices
Leanpub Ebook: leanpub.com/cpp23_best_practi...
► C++ Best Practices
Amazon Paperback: amzn.to/3wpAU3Z
Leanpub Ebook: leanpub.com/cppbestpractices
JASON'S PUZZLE BOOKS
► Object Lifetime Puzzlers Book 1
Amazon Paperback: amzn.to/3g6Ervj
Leanpub Ebook: leanpub.com/objectlifetimepuz...
► Object Lifetime Puzzlers Book 2
Amazon Paperback: amzn.to/3whdUDU
Leanpub Ebook: leanpub.com/objectlifetimepuz...
► Object Lifetime Puzzlers Book 3
Leanpub Ebook: leanpub.com/objectlifetimepuz...
► Copy and Reference Puzzlers Book 1
Amazon Paperback: amzn.to/3g7ZVb9
Leanpub Ebook: leanpub.com/copyandreferencep...
► Copy and Reference Puzzlers Book 2
Amazon Paperback: amzn.to/3X1LOIx
Leanpub Ebook: leanpub.com/copyandreferencep...
► Copy and Reference Puzzlers Book 3
Leanpub Ebook: leanpub.com/copyandreferencep...
► OpCode Puzzlers Book 1
Amazon Paperback: amzn.to/3KCNJg6
Leanpub Ebook: leanpub.com/opcodepuzzlers_book1
RECOMMENDED BOOKS
► Bjarne Stroustrup's A Tour of C++ (now with C++20/23!): amzn.to/3X4Wypr
AWESOME PROJECTS
► The C++ Starter Project - Gets you started with Best Practices Quickly - github.com/cpp-best-practices...
► C++ Best Practices Forkable Coding Standards - github.com/cpp-best-practices...
O'Reilly VIDEOS
► Inheritance and Polymorphism in C++ - www.oreilly.com/library/view/...
► Learning C++ Best Practices - www.oreilly.com/library/view/...

[@N....]

The halting problem is one of my biggest pet peeves in computer science because so many people misrepresent it by claiming it has any relevance to real world computing. The halting problem is only a problem when you have infinite memory, which real world computers cannot have. Therefore any program that tries to recursively run the judge and output the opposite will eventually run out of memory and halt. It's also an unnecessarily narrow set of outcomes. Super interesting in the theoretical realm, but utterly useless in real world computing. We have static analyzers already, which some people seem to think impossible due to the halting problem. We can get more nuanced results other than "halts" or "doesn't halt", for example we can find out how much memory would be used as well as whether or not it tries to somehow do the impossible task of figuring out what static analyzer is analyzing it and run its own copy of the static analyzer for reasons nobody knows.

[@ConceptInternals]

There is a difference between static analysers able to catch "many common problems" and "all problems". Without going into halting problem, no one can prove that a static analyser will catch all cases.
Say, we wrote a function for 3n+1 problem. Given enough time and memory, static analysers can see that the function will terminate for all 32 bit integers, it doesn't mean static analysers should try to cover all cases here

[@dukex123]

Keep in mind that a program can run and do work forever without using more memory. I don't know where the idea comes from that a program will continuously consume more memory the longer it runs.
In the real world are many programs that do not do that. And must not due that, due to the expected runtime. Which can last to decades.

[@quintrankid8045]

I don't see why infinite memory is a requirement. I cribed this from Wikipedia,
def g():
if halts(g):
loop_forever()
halts takes a function as its argument and returns true if the function halts, false otherwise, but this leads to a contradiction.

[@ConceptInternals]

@@quintrankid8045 in this example, stack memory will be filled due to recursive calls

[@SomebodyHere-cm8dj]

also, a lot of theoretically unsolvable problems can be solved "good enough" with heuristics

[@ranseus]

OK, but... so what? Maybe the point is "doing" the work, and not "completing" the work.

[@quintrankid8045]

That's a different problem.

[@mytech6779]

Can you give an example? Just a machine whizzing and chugging and making heat in a sealed room with no output doesn't appear to have much point.