This one gets a lot of technically competent people.
I spent a very unsatisfying 45 minutes vainly trying to explain to an eminent biologist that no, really, some statements really are _undecidable_ -- and no, that doesn't mean that at some future time we'll figure out a new approach that lets us decide them.
He challenges the team by asking them to speculate about options, if they managed to "disrupt" the industry by breaking that speed barrier, and gets mighty upset by these closed-minded engineers who are unwilling to accept any possibility of a breakthrough
Although the laws of physics can't be broken, in certain scenarios we can simulate we have done just that. And often that's just what you need to get ahead of your competition.
"You're saying we can't do HFT between Tokyo and New York faster than the speed of light? Here's a completely unrelated product, that does something completely different, and the limit they're working with doesn't really apply to us. So it is possible! Maybe you should go to Burning Man, that would open your mind.."
The interface between plain language and math is messy. I don't think I've ever seen something suggested that was actually mathematically impossible. Even the halting problem is easily solved in practice.
I never seen anyone serious ever claim that cryptographic backdoors are impossible.
> Even the halting problem is easily solved in practice.
Like, how exactly?
But, actually, the most straightforward way to show that most 'everyday' programs terminate is -- assuming functionality of the language runtime as stated -- that they typically consist of non-recursive functions or functions on structurally smaller inputs. It would be obnoxious, but not difficult to show that a program like 'grep' terminates, assuming functionality of the operating system and hardware on which its running. This is actually fairly straightforwards, and many many functional languages with a focus on correctness have totality checking builtin. For example, Idris and Agda.
Of course, if you're going to ask to prove both functionality of the operating system (like Linux + glibc) or the processor itself, then that could indeed be trickier. But, if you limit your stack, it's certainly possible. The truth is that most computing does not consist of solving Turing complete problems.
Now if we are actually discussing in good faith, the halting problem is often used as a reason why a particular program analysis wont work. While a good guideline, it does not mean that there are particular classes of programs for which these analyses would work. If you can show this and show that these programs cover a good amount of useful programs, then you can construct analyses that a purely theoretical and cursory understanding of the halting problem would suggest you cant. Indeed several useful languages do just this
Now from a realistic standpoint, all they wanted was some evidence we had considered this possibility and some data/argument to show our confidence that it wouldn't.
This was a simple program - you could confirm the algorithm wouldn't run forever by examining the code - look at the loops and their termination conditions, and look at function calls to show there were no loops in the call graph, etc. Yet one engineer in the team refused to engage. He kept invoking the halting problem. At one point I asked him that if the program was simply 'print "A"' would he still refuse to make the claim? Yup. No idea what the compiler/interpreter/HW is doing behind the scenes.
In the real world, when someone asks you to give an idea as to whether the program could hang in an infinite loop, don't invoke the Halting Problem. You're not answering the question they think they are asking, and as an engineer, your job is not to be pedantic with customers - unless you want to lose them fast.
That was in a C# shop so of course the "decision" was never implemented. My guess is that this was a completely mad decision taken by non-technical managers in a moment of panic, who had pressed our tech lead a bit too much on why software breaks and what can be done to avoid it breaking- and then latched on to some off-hand comment about recursion being an alternative to iteration, and ran with it.
I am a web dev who knows nothing of the Collatz conjecture, so I had to check out the Wikipedia article for it. Thanks for teaching me something today.
I wrote this JavaScript function based on what I read in the article. It's a simple algorithm but it was fun to see it work. For anyone who is in my shoes (weak mathematical background), running this function might be a useful supplement for illustrating the gist concept of the Collatz conjecture:
function collatz(i) {
console.log(i); // for visual feedback
if (i <= 0) throw new Error('Input must be a positive integer');
if (i === 1) return i;
if (i % 2 === 0) return collatz(i/2);
return collatz((3*i)+1);
}
collatz(42); // or any positive integer(tongue in cheek, of course, but I think the OP is trying to capture a similar pragmatic view of the halting problem)
no, it's not. Knowing that this specific program halts or not doesn't address the issue.
Cryptographic backdoors are possible (See Clipper and LEAF for previous examples). Cryptographic backdoors that will only ever be used "legitimately" aren't, and legitimacy isn't a mathematical concept.
You don't grok what the halting problem is. What you're describing (I assume) is determining if a specific program is going to terminate. That's not the same problem.
From Wikipedia:
Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.
Yes it isn't literally solving the halting problem. But I've had a weird number of people tell me that the stuff I work on doesn't work because of things they learned in undergrad.