Thread: The fastest machine?

I was interested to hear the direction that this thread took - and thought it might merit further discussion in its own thread.

It got down to brute force for solving certain problems computationally, and as i may *ahem* coin it.. ;-> ..deductiveCentric, versus logicCentric algorithms to do so.

In a perfect machine code submission I believe that a perfect deductive would beat a perfect brute force. Or would it? Is it not the nature of computing that it is most suited to just crunching numbers - ie generic to the machine? Does our brain operate in a deductive manner? at the base processing level? Or is it just harnessing the sheer hardware capability?

[EDIT] I am thinking now in terms of weather forecasting and the like - chaos based approximations, or the merging of many scenarios are employed - not just the crunching of scenarios themselves - but that is forecasting, which is not seeking a known goal- like sudoku solving or peg solitaire solving i suppose

I believe in depends on how the "fastest machine" would operate.

If it was a quantum computer, then the brute force may be both faster and surely more accurate.
If it was a conventional computer, then the deductive would probably be less accurate, but it'd also be much, much faster.

Originally Posted by GReaper

...If it was a conventional computer, then the deductive would probably be less accurate, but it'd also be much, much faster.

...Unless there are too many branch mispredictions, so that's not a given.

Originally Posted by Elysia

...Unless there are too many branch mispredictions, so that's not a given.

Well, of course, all algorithms have best, worse and average case complexities, and I don't think that's something the machine can predict or hope to compensate for completely.

But even if a branch misstep took a million more cycles to complete than a normal iteration, if the brute force had a billion more iterations to complete than the deduction one, you can see which would take longer to complete.

Unless you're joking, it which case... I don't get it.

Originally Posted by rogster001

In a perfect machine code submission I believe that a perfect deductive would beat a perfect brute force. Or would it? Is it not the nature of computing that it is most suited to just crunching numbers - ie generic to the machine?

If you can't reason with it, crush it.

This is implied human nature. But it is also how you find the optimum solution to solve a problem. What it means is that not always you can come up with a deductive solution to a given problem. And in that case, a brute force algorithm is both a necessity and a guaranteed win.

Some problems don't have deductive solutions. We simply don't know yet enough about them to create valid premises and syllogisms (therefore we cannot achieve verifiable solutions). Other problems may have deductive solutions, but these do not fit well in the computing paradigm (another implication in GReaper answer) or aren't optimal enough to beat a straightforward brute force solution.

An example of a problem without a deductive solution is any currently unsolved problem, like the Travelling Salesman Problem, or the Twin Primes Conjecture. An example of solvable problems with deductive solutions that are less optimal than brute force methods is The Four Color Theorem, in which one of the deductive proofs is composed of several hundred pages of mathematical formulations. Chess endgame solutions are also notoriously easier to compute through brute force, compared to the possible deductive alternatives.

So it is indeed possible to come up with better brute force solution to a problem known to also have deductive methods. Two major factors will dictate when this is desirable:

- There exists a set of heuristics that remove a large portion of the test cases. Meaning, usually only problems from which heuristics can be devised are good candidates for brute force methods.
- We aren't tasked with finding all possible solutions (or all invalid cases), but we are content with just finding a solution or a manageable set of solutions.

Weather forecasting is one example you gave of a problem in which you really have no other option than to provide a brute force method because it is largely an unsolved problem. But, like with most scenario modelling programs, there are already some deductive algorithms that can be applied. So it's in fact an hybrid method. Likewise, it is (at least presently) rich in heuristics that will most likely always ensure a brute force method is going to always be a more desirable approach.

Does our brain operate in a deductive manner? at the base processing level? Or is it just harnessing the sheer hardware capability?

Honest answer? We don't know. But this is one myth I would like to see come to an end...

Our brain is not necessarily a good computer. Probably it is a most terribly noneffective one that, once we learn more about it, we will probably also learn to accept the idea that perhaps it is time to put a rest to this nonsense that our computers should try to mimic our brain processing power.

And I'm saying this because we have hints about our brain lack of capabilities everywhere. Can you solve complex mathematical expressions in your brain, or is it not a fact that you can only use it for small step calculations and you need the help of your visual cortex and several seconds or minutes of thinking to both perform the step and make sure you did it correctly? Likewise, can you reliably store information in your brain, or isn't it a fact that you can't and that this is precisely why some of our mental capabilities are speedy but necessarily unreliable?

In the evolutionary history of the human brain, we are still in the last seconds of the 31st of December, if I'm allowed the gross interpretation of Car Sagan's famous allegory. To me at least -- and looking at how unreliable and slow thinkers we are -- I think we are still holding baby brains in our heads that require a whole lot more of evolution to do to catch up with the problem solving requirements of reliability and speed.

Despite our brains, we did have to invent computers, didn't we? So why do we want to make them like our brains?

Originally Posted by GReaper

Well, of course, all algorithms have best, worse and average case complexities, and I don't think that's something the machine can predict or hope to compensate for completely.

But even if a branch misstep took a million more cycles to complete than a normal iteration, if the brute force had a billion more iterations to complete than the deduction one, you can see which would take longer to complete.

Unless you're joking, it which case... I don't get it.

I'm just saying, there may be some problems where there are just so many branches that causes branch mispredictions that a brute force way is just more efficient.
I believe that this is actually the case is some more cpu insensitive algorithms, like those used in video encoding. Even though it might mean less computations with branches, they're avoided because of the penalty for a branch misprediction.

Despite our brains, we did have to invent computers, didn't we? So why do we want to make them like our brains?

I suggest - To help build things that can do what we can, not just what computers can

Our brain is not necessarily a good computer. Probably it is a most terribly noneffective one that, once we learn more about it, we will probably also learn to accept the idea that perhaps it is time to put a rest to this nonsense that our computers should try to mimic our brain processing power.

The hardware seems similar, but yeah our brains are horrible at putting all of their resources on a single task. Plus there is all the faulty logic caused by vestiges of the things that helped us all survive a long time ago.

As far as thought goes, most people think inductively rather than deductively. This makes sense in most cases as it is the fastest way to reach a conclusion, which may have been important in life and death scenarios.

In programming terms inductive thinking might be something like taking an element and performing some sort of "closest match" search against another collection you have memoized, then storing the results in the memoization memory. This is why people change their minds so slowly even against evidence, their past experiences are informing how they think about a thing currently.

Originally Posted by Alpo

As far as thought goes, most people think inductively rather than deductively. This makes sense in most cases as it is the fastest way to reach a conclusion, which may have been important in life and death scenarios

It is not about what makes sense, but what it really goes on inside our brain. And the scientific answer is: we don't know.

And neither can we say something like "most people think inductively". Given that we all share a similar biology as members of the same species, it is a given that whatever core mechanism we share it is going to be common across all members of our species.

But more importantly, reasoning methods (deductive, inductive, abductive, and analogic) are inference methods that live above the core physical processes that permit logic building. They are higher level abstractions and do not represent any sort of fundamental physical property of our brains.

This is true of the human brain as is of a computer. Whatever physical mechanism our brain uses to reason, it cannot be called deductive or inductive or whatever. That physical process is a core process that allows for any of those methods to then be used on top of it. Much like the binary processing happening inside a computer allows for all manner of different abstractions to be created.