Halting Problem Undecidability - the most concise (1-minute video) COMPLETE proof ... but is it correct? Computer Science

---

Halting Problem Undecidability - the most concise (1-minute video) COMPLETE proof ... but is it correct? Posted: 23 Aug 2021 03:50 PM PDT I made a video about Halting Problem and it's Undecidability: https://youtu.be/3SM7zpDF3pU The video is super fast paced because I wanted to qualify for Veritasium Contest. If you are new to the problem, you'll likely need to pause and rewatch a couple times to understand it. Let me know if you have any questions - I'll answer:) The question I have though for more experienced math-logicians: Is it indeed correct and complete? // Assume that algorithm 'halts' exist // npm install --save halts import halts from 'halts.js'; function f() { if (halts(f)) while (true) { } else return; } f(); This proof is typically (on Wikipedia, for example) portrayed as merely a proof idea/concept, but after pondering about it for quite some time, I am convinced that this is a complete proof. In short It is correct because there are no errors With details (everything written here has an asterisk (*): "as I understand") It would not be complete in lambda-calculus "computational model", but it is complete in "standard" computational model, by which I mean typical programming languages like JavaScript or Python, where: Functions can reference themselves and You have access to function content/definition/code by reference Try running "(function f() { return f.toString(); })()" in JavaScript, for example In lambda calculus: Functions can't reference themselves (solved by introducing one parameter and passing function it's own reference - typical recursion simulation) You can't get function-code by "reference". Having received function as a parameter, you are only allowed to execute it, but "halting algorithm" should have full access to the content of the function in question (solved by passing function-code, instead of function itself) Because of these two, proofs in lambda-calculus are longer than my proof. And if you want to prove it with Turing-machines, because they are so limited, you'll have to do even more work than with lambda calculus. The questions why Lambda-calculus and Turing-machines are equally powerful/expressive as, say, JavaScript - are interesting questions, but those are separate questions which in no way invalidate the proof. The fact that it is a complete proof and not a proof-concept, seems like an unconventional viewpoint, so I expect there might be errors somewhere in the reasoning. Any clarifications, elaborations from experienced people are appreciated, as well as questions from new-commers:) submitted by /u/nns2009 [link] [comments]

You are subscribed to email updates from Computer Science: Theory and Application. To stop receiving these emails, you may unsubscribe now.	Email delivery powered by Google
Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, United States