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.
A very short example.
Let's say you need to write a program that get three variables:
a is an integer.
b is an integer.
op is an operand (can be only
Lets say you know how to calculate
a+b and also
You also know how to process what
op is (
All that is left is to perform the relevant calculation.
How do you suggest doing this without a
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.
There are many, many different ways to perform computations, but any general-purpose computer has some form of conditional execution, and some way to repeat a computation with different data.
We have invented many models of computation, and it turns out that all the ones we think of as sufficiently powerful are equivalent. A sufficiently powerful model of computation is said to be Turing complete. There are of course models of computation that aren't Turing complete, but they feel restricted: you can't do as much with them. Pretty much all programming languages are Turing complete if you ignore the fact that computers have finite memory (and reasoning about computers with large but finite memory is so hard that we normally approximate the memory as infinite).
A computer that doesn't have any way to compute conditionally or to repeat a computation can effectively perform only the particular sequence of instructions that it was programmed to do. That lets you define some simple operations, but not much. If there's conditional execution but no repetition, then the program can behave differently depending on the data, but there is effectively a finite number of different behaviors. If there's repetition but no conditional execution, then a program either always terminates or never terminates, there's no way for a program to terminate or not depending on the data. To write all possible programs, both conditional execution and repetition are necessary.
In practice, to write most interesting programs, both conditional execution and repetition are necessary. Exactly what programs you can write without them depends on what basic operations you allow, but it won't be much. For example, if you only have the basic four operations on integers (
/) then something as simple as primality testing can't be done without repetition (e.g. to repeat trial division) and branching (to exit the program once the answer has been found).
Conditional execution and repetition aren't enough to be Turing complete: you also need some way to use an unbounded amount of memory. But that's a story for another time.
In low-level imperative programming, conditional jumps are the usual way to implement conditional execution and repetition (you repeat by jumping to an earlier point in the program). In a higher-level imperative program, repetition is expressed via looping.
In other models of computation, conditionals and repetition may be derived from other primitive functionality in a non-obvious way. For example, one of the most important models of computation, the lambda calculus, does not have a conditional feature or a repetition feature per se. Lambda calculus has just one computation rule, called beta reduction: “if you apply the function that maps $x$ to $M$ to the argument $N$, then the result is $M$ in which $x$ has been replaced by $N$”. It indirectly permits repetition because there can be many occurrences of $x$, and so $N$ is repeated. It indirectly permits conditional execution because the lambda calculus doesn't distinguish between data and code, and the argument of a function can be treated as a function and executed, resulting in behavior that depends on the argument. So conditionals, repetition and unbounded memory (like repetition, arising from the repetition of the argument in the substitution) are all present.
In fact, conditional branching and unbounded memory are all you need to make a Turing complete model of computation. A suitably-chosen one-instruction set machine is Turing complete. Many such instructions involve a subtraction in addition to the conditional branching, because it's convenient, but arithmetic is not actually necessary, it's just convenient to access memory. Turing machines, another very important model of computation, doesn't include anything like arithmetic, just conditional branching (inside the finite automaton, conditional because it depends on the value read from the tape) and the tape for memory. Likewise the lambda calculus doesn't have anything like arithmetic in its rule, but you can build arithmetic above the lambda calculus.