Cheap and Secure Web Hosting Provider : See Now

[Solved]: Why does computer have branch and jump instructions

, , No Comments
Problem Detail: 

I could guess why computers have arithmetic operations like add, sub, and mult instructions. It is to compute numbers, but I don't get why branch and jump instructions exist. I am asking what theory or purpose for implementing branch and jump instructions is there? I've tried to get rid of branch and jump instructions and what effect it will cause on the computation, but I could not get the result.

Asked By : Ji-Yong

Answered By : Andrej Bauer

Theoretically speaking you do not need any branch and jump instructions. This is so because you can encode them into artihmetic. For instance, instead of writing

if p:    x = a else:    x = b 

you can write (assuming that $0$ stands for "false" and $1$ for "true"):

x = p * a + (1 - p) * b 

Gödel was the first to have realized that when he proved his incompleteness theorem, namely that arithmetic sufficies for all of programming, theoretically speaking. So in this sense you are correct.

Supplemental: we do need some sort of iteration or recursion, as was noted in the comments. By "arithmetic" here I mean general recursive functions which have recursion built in. There is a form of "conditional" in recursion, namely the distinction between zero and a successor.

However, it is impractical to insist that arithmetic is somehow the most important thing. There are many different ways to do computation. For instance, we do not even need any arithmetic or recursion, we could use just pure $\lambda$-calculus, which is a pure theory of functions, without any numbers, booleans, or any other form of data (they can all be built up). Which paticular form of computation should be used actually depends on many factors: What does the hardware support? What makes programming most maintainable? How do we make programs efficient? And so on. The actual programming languages and CPUs that we know today are the result of many years of experience. It's turned out that it's better to have conditional branching than not.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/64664

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback