Words of the Week: Heuristic [& Algorithm]

Isaac and I were debating the meaning of Heuristics the other day, trying to come to some common ground.  We ended up going into some interesting places, but it lead into a good question about what they are and how they are used.  Let me start with my off the cuff definition using no wiki links, then we'll hit into a more formal look.  A heuristic in my mind is a way of getting a not always right answer, but an answer one hopes is good enough.  In comparison, an algorithm will always provide a 'correct' answer.  This means that the output is consistent given the input and will always provide the best answer it can. This leads into the question of, can a computer give a non-algorithmic (heuristic) response?

Now when Isaac and I were talking through this, he noted that a computer always gives the same answer if you lock down all of the inputs.  Random.Int() uses a seed, and if you replay with that same seed it will do the same thing.  If you change the configuration or time of the computer and that has an affect, that is an input, and in theory if you lock that down too as an input.  If the number of CPU cycles for the process is an input, that too would be locked down.  Now given my informal definition, are all heuristics really algorithms, just with inputs that are hard to define?

Lets flip this on its head.  What about people?  Isaac asked me, "What would you call that plant?"  I said, "Green" to his chagrin.   He said, "No, the name of the plant is?"  A co-worker interjected, "George."  Obviously it wasn't Isaac's day, but the point Isaac was going for was, if I didn't know the name and then he told it to me, would I then be able to get a closer to accurate answer.  Even if Isaac was wrong, I had some knowledge base to draw on and could use that to give a heuristically better answer, but I could still be wrong, given that the name might also be George.  The problem is...  What if we locked down all of my life experiences, genes and repeat the experiment?  Obviously it can't be done, but am I really an algorithm that is just a walking input/output device of large complexity?  We are hitting into the realm of determinism and free will.  Is everything an algorithm?  I don't really want to get too far into the weeds, but I believe a point will emerge from this.

The time is now that we start looking at more formal and test oriented definitions to Heuristics.  In wiki it says,

In computer science, artificial intelligence, and mathematical optimization, a heuristic is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution. This is achieved by trading optimality, completeness, accuracy, or precision for speed.

 Bach and Kaner say,

A heuristic is a fallible method of solving a problem or making a decision.

So now that we know that, I want us to be able to contrast it to Algorithm, the other word that incidentally is being considered.  Again, let us consider wiki:

In mathematics and computer science, an algorithm is a step-by-step procedure for calculations. Algorithms are used for calculation, data processing, and automated reasoning.  ... While there is no generally accepted formal definition of "algorithm," an informal definition could be "a set of rules that precisely defines a sequence of operations."

In both definitions, Heuristics acknowledge failure as a possibility.  On the other side, the Algorithms definition notes that their is no formal definition and the only 'failure' I noted that was somewhat on topic was the question if an Algorithm needed to stop.  If an Algorithm does not care if it gives back a correct value, just that it has a set of finite steps, then it too acknowledges failure is allowed.  In theory, some might note that it should end eventually, depending on if you think a program that has a halting state is an Algorithm but this is the only question about outcome.  I suppose you could say an Algorithm can also fail, as success is not a required condition, only halting.  In all the definitions, their is some method for finding a result.  The only difference appears that Heuristics specifically acknowledge limits and stopping points and Algorithms don't.

So what is the difference between Heuristic and Algorithm?  One of the popular StackOverflow answers says:

• An algorithm is typically deterministic and proven to yield an optimal result
• A heuristic has no proof of correctness, often involves random elements, and may not yield optimal results.

So in this very formal world, an Algorithm requires mathematical proof of correctness (within a given context, such as assuming our universe's constraints).  Heuristics on the other hand need no such formal proof.  In that case, most code is in fact Heuristical in nature and most of our testing is also Heuristical in nature.  This starts to lead into the question of sapient testing vs checking, but still, I don't want to get into that yet.  Well not much.  I do want to address one other quote from Bach,

There are two main issues: something that helps you solve a problem without being a guarantee. This immediately suggests the next issue: that heuristics must be applied sapiently (meaning with skill and care).

The idea that Heuristics require skill and care is an interesting one.  When I write an automated test or when I write a program, I use skill and care.  Am I using Heuristics in my development or is my Algorithm the Heuristic?  When I test, am I exploring a system using a Heuristic but when I write automation, the Heuristic of my exploration is lost after the writing of the test, and then it becomes something else, an Algorithm to formally prove if the two systems can interact the same way controlling for the majority of the inputs?  What happens when computers start getting vision and understand a little of the context?  Are they now sapient in a given context (meaning are they skilled and take care to manage the more important aspects compared to the less important aspects)?

I don't intend on going on in this questioning manner, but rather to hit you with a surprise left.  Sometimes, words are so squirrelly, that when one person attempts to pin them down, they end up creating a unintended chain of events.  They create just another version of the meaning of the word.  Next thing you know, no one really knows what the word means or what the difference is between two words is.  I have done way more research on this than most do, and yet I don't think there is a good answer.  I too will attempt to put my finger in the dike, but I don't expect to stop the flow of definitions:

• A Heuristic is an attempt to create a reasonable solution in a reasonable amount of time.  Heuristics are always Algorithmic in that they have a set of steps, even if those steps are not formal.
• A Algorithm is a series of steps that given the control of all inputs will consistent give back a result without necessarily considering other external factors, such as time or resources.  These steps have some formal rigor.