17

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?

  • 11
    You cannot demonstrate by example that something is impossible. Your coworker will just say "It's not working because we haven't figured out the correct approach". The best you can do is show him a proof. If he doesn't buy it, he's either really stupid or a moron or both. Here's a list of undecidable problems: en.wikipedia.org/wiki/List_of_undecidable_problems – Thomas Eding Jan 16 '14 at 22:42
  • 18
    A theoretician and engineer were told they could kiss a girl by repeatedly travelling the distance between them and her by half. The theoretician immediately gave up saying "it's impossible, I'll never get there". The engineer went for it, saying "I'll get close enough for practical purposes". You, sir, need to try for that kiss. – gbjbaanb Jan 17 '14 at 8:51
  • 2
    @gbjbaanb: That's a good descriptor of many of the non-optimal solutions to NP-hard problems, and knowing those problems are (practically) impossible to solve classically is why you go for the alternative method. If you don't accept that some problems are either practically or literally impossible to solve then you'll not look for imperfect solutions that may give a "good enough" answer after an indeterminable period of time. – Phoshi Jan 17 '14 at 9:27
  • 3
    @Phoshi nope, the point is that real-world engineering solutions only require a solution that is good enough to solve the problem sufficiently for acceptance. Solving it perfectly is not worth the time and expense. eg. Travelling salesman problem is impossible given more than a few nodes, but a less-than-optimal solution is still required (and delivered) by many businesses. If we only produced perfection, no-one would have these. – gbjbaanb Jan 17 '14 at 9:34
  • 10
    @gbjbaanb: True, but the only reason they solved those problems is by first accepting that you can't "do anything with enough time and money" and stopped chasing the optimal solution. The knowledge of what you can't do is often just as important to finding a solution as the knowledge of what you can do. – Phoshi Jan 17 '14 at 9:40
11

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.

  • 14
    The halting problem comes out in static analysis of code. From this you can get mundane problems like "here is some code, make it look pretty" to "here is some code, is it malware" - the first is business important for companies making IDEs (syntax highlighting, refactoring), the second to anti-virus companies and security professionals. – user40980 Jan 17 '14 at 1:31
  • 12
    "Similarly, the Halting Problem is important to theorists, but it doesn't have much relevance to most businesses.": Well, if the halting problem were computable, we could automatically check if a piece of software is going to terminate / hang on a certain input or not. We would probably have no BSOD's any more. Since this is not possible, we have to use other techniques to ensure software quality (such as testing) and no one is investing time and money to develop a general "termination check" program. So I think this theoretical result has a huge practical relevance. – Giorgio Jan 19 '14 at 13:29
4

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 :)

  • Your second quote attempts to invoke the halting problem incorrectly; however if we know the COBOL program works and can execute it in a test environment (vm-clone all PROD if need be) the halting problem is excluded and we may attempt. Probably by hand rather than by program but all the same we can do it. We could tree-bisect all possible input forms if need be. Because the target program halts, so will the tree-bisect. – Joshua Jan 31 '14 at 22:30
2

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.

  • 1
    (3): Fail to get another job after the market finds out you even attempted both – TruthOf42 Jan 31 '14 at 21:15
1

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).

0

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.

-6

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.

  • 2
    The essence of the halting problem is that there are classes of problems that cannot be computed, ever - even with infinite time and money. That is what my coworker refuses to accept. – Jesan Fafon Jan 20 '14 at 17:28
  • Then we disagree. I've edited my answer, but essentially the message is the same. Your question as posed does not have an answer (or not one you will like), but underlying it is a real issue and a real point to be made. If you want to win this argument, you're going to have to shift ground somewhat, and I've tried to provide some help in doing that. [Remind me not to try to answer questions like this again -- the negative votes are unwelcome.] – david.pfx Jan 21 '14 at 1:58
  • 2
    @simon: At the risk of repeating myself, there are no programs that take an infinite amount of time to complete because there are no Turing complete computers, just finite approximations to them. You cannot prove that an arbitrary program will complete in any particular amount of time by any method that is quicker than actually running the program. In practice, any sentence with the word 'infinite' in it runs the risk of making no sense. – david.pfx Jan 21 '14 at 11:11
  • 3
    while True: print "doing stuff"; print "Finished"; That is an example of a program that takes an infinite amount of time to finish. There is an infinite amount of other programs that also take an infinite amount of time to complete. We regularly create programs that take an infinite amount of time to complete on purpose. They are called 'long running processes'. Most dynamic websites are examples of one. – Singletoned Jan 21 '14 at 23:28
  • 2
    The point is surely that there are sets of computer programs that are effectively infinite, they'll never stop under their own steam (we will press break, pull out the power etc. eventually), if we programmed them into a Turing machine it would run without stopping. The essence of the halting problem is there's no way practically or theoretically to determine non-halting programs at all algorithmically. – Alistair Mackenzie Jan 22 '14 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.