I have coworker who refuses to accept the reality that Turing machines (and Von Neuman machines by extension) cannot solve their own halting problem stating:
You can do anything with enough time and money.
He also dislikes theoretical problems arguing that:
In our field, we'll never run into those questions. We're application developers, not theoretical scientists.
Is there a good example of a business problem that is computationally impossible that I could use to help convince him of this?
Not technically impossible, but...
Scheduling resources, with the goal of finding the ideal schedule that maximizes the use of time slots. I was on a project once, in my earlier computing days, that had this requirement. I worked on it awhile before I realized that it was NP-hard.
Other examples of problems that are not technically impossible, but are technically difficult, can be found here.
Most hard computational problems in business computing are not impossible, just impractical. Your friend is right; you can solve most of them if you throw enough money at them. But the argument is specious; the whole point of running a business is to make money, not lose it.
In daily practice, we talk about Turing completeness in a vague way, not to demonstrate some mathematical principle, but to illustrate (for example) the inadequacy of HTML and CSS as a complete vehicle for producing feature-complete programs.
Similarly, the Halting Problem is important to theorists, but it doesn't have much relevance to most businesses.
Others have commented on this, but I will try to write out an answer giving my point of view.
I like Robert Harvey answer, and the comments to his answer, and I would like to expand on those.
I think you have to present these undecidable problems (like termination) in a mundane way: for example, an IDE tool that "checks if this function always returns a value".
When teaching, my favourite example was refactoring (function equivalence, another undecidable problem). I asked:
how do you check if a function/program does the same after your nice refactoring? Sure, we have unit tests for that, but they do not cover all the cases. And they are boring to write... But we are programmers! We should write a program that checks if these two functions are producing always the same result! Why don't you try to write it?
or, as a variation maybe closer to your case:
We have this legacy code written in an ancient obscure COBOL dialect, for which no spec and/or compiler exist. We only have the program. Our whole business relies on it, so we have to be 100% sure the new Java code does exactly the same in every situation. Management wants a program that do that, checking all possible cases, and estimates it can be done in 6 to 8 weeks. Why don't you try to write it?
The point is not to write such a program. Or a good enough approximation of the requirements. The point is to realize that it can NOT be done in a direct way, do NOT waste countless ours trying to figure out how to do it (only to realize that it is not possible), but recognize it. "Ah! this is undecidable! It is not possible to do it directly. I need to figure out a different, more clever way to do it, with a good enough approximation".
You have to figure out a way to present the problem in a recognizable, and apparently simple, way. You wouldn't believe how many CS students will try to write such a program straight away... before taking a computability class :)
Assuming we may set aside moral questions aside for the moment:
Business A has contracted to you for a way to communicate between satellite offices A1 and A2 without anyone besides the authorized people in A1 and A2 being able to understand the communication.
Business B has contracted to you for a way to intelligently eavesdrop on all communications between A1 and A2.
Obviously you can't do both.
Due to the way the math works out (the exact math has been subject to ongoing research for 100 years), one of the following requirements cannot be satisfied:
(1): Provide an encryption algorithm that cannot be broken by an attacker with an arbitrary amount of money available.
(2): Provide an encryption breaking algorithm for an arbitrary encryption algorithm that runs in a reasonable time.
I have taken a class recently on Business Process Model and Notation (BPMN). There it can easy be seen that workflows with many too splits, joins and loops become quickly impractical (though not necessarily impossible, AFAIK) to understand and control, (when you use too many OR-splits instead of XOR-splits).
For the software industry, I think the same holds for similar problems of "multiple condition coverage" in code coverage analysis.
For a business, the way to go is to shrink the problem space, and not to throw more resources at the complex problem. In my example, add constraints to the workflow, (or in code coverage analysis, simplify the code), instead of working hard on finding all, say, N possible traces and outcomes where N is an unimaginably large number.
Aside from that I think there are many problems in network / graph analysis that are impossible to solve (trying to determine a network topology by iteratively walking all paths etc).
The classic example is trying to parse HTML with regular expressions. This can work with limited sets of HTML but a general solution is impossible, due to the fact that they have different Chomsky grammars (as the link makes clear(ish)).
More generally some people don't like to think philosophically (like your co-worker) and I'm not sure you can argue your way out of a mind set. His first point is certainly wrong but his second might just be a way of saying I don't need to worry about this to code web forms for goods receiving. I've got some sympathy with this but sometimes knowing the theory means you don't commit yourself to finding the Holy Grail on work time.
Perhaps the answer is that your co-worker is correct. Perhaps you have misunderstood Turing, or how it applies here?
All machines are finite, therefore there are no 'real' Turing machines and no programs that will never halt. A trivial program that executes a simple infinite loop could run 5 minutes or 50 years but on a finite machine it will halt. A non-trivial non-halting problem such as 'calculate pi exactly' will also halt, because eventually the calculation will exceed the capacity to store further digits.
The Turing result does not guarantee anything particularly useful on finite machines, so your quest is ultimately fruitless. Better to focus on how much time and how much money and leave infinity to the mathematicians.
You may think that a program like { while true: print "running"; print "halted"; } is a counter-example but it is not. This program has side effects, which may or may not cause it to halt. Ignoring the side effects, it is possible to devise a formal proof that this program will not halt. In this question we are only concerned with programs that evade formal proof of non-halting, where the question of halting is undecidable. This is not such a program.
It may help to distinguish 'strong' Turing from 'weak' Turing. Strong Turing machines are actually infinite and if they fail to halt, will run for infinite time. We cannot build those.
Weak Turing machines have finite limits on time and space, and they are the only kind we can build. We are interested in programs that cannot be proven to halt within those limits. Turing tells us that there are such programs but we cannot identify them. If the limits are low enough we can identify them by writing the program and running it to its limits.
The essence of Turing is that there are no shortcuts. The only way to be certain whether a problem is computationally feasible is to write the program, run it and find out. With enough time and money you can write all the programs, run them forever and over time, and find the ones that produce results (the halters). The others will still be running. Does you co-worker have enough time and money to do that?
Seriously though, the dispute is about limits. Turing and NP complete tell us that certain classes of problems cannot be solved by computers within any given budget or on any given schedule, no matter how large that budget or how generous that schedule may be. Examples of that kind of problem abound: breaking cryptographic keys; optimising the routes for making deliveries to hundreds of addresses; packing boxes in trucks; finding bugs in large programs!
So ask your co-worker for a budget and a schedule, and make a promise that you can produce a problem that cannot be solved within that budget or schedule. That promise will be very easy to keep.
