Algorithms lie at the heart of computing. When you surf the web, you open up a web browser. When you view a website, your web browser takes the HTML file, which contains code, and then the browser uses an algorithm to convert the code into a page that actually makes sense to humans. When you listen to music on iTunes, the music player takes the MP3 file, which encodes the sound as 0’s and 1’s, and it uses an algorithm read the 0’s and 1’s and tell your computer speakers to output sound. When you’re looking for a particular song in your music library, you might want to search alphabetically, so you click on the Name column to sort your songs alphabetically. Your computer doesn’t magically know how to sort your library. It follows a precise set of instructions every time it’s told to sort something. That set of instructions is an algorithm!

Modern electronic computers actually follow a theoretical model invented by Alan Turing in the 1930s. This theoretical model, now called a Turing machine, can be informally described quite simply. A Turing machine is composed of three parts: states, a tape (consisting of blocks or cells), and a tape head, which points to a cell. The modern computer counterpart to the tape is memory, and the counterpart to the tape head is the program counter. In addition, the Turing machine has a transition function, which tells it which state to go to and what to do on the tape, given its current state and tape contents. Think of it this way: you have a set of states such as “hungry”, “sad”, “happy”, etc. and you have a row of infinitely many sheets of paper laid side by side on the ground, but they’re so big that you can only see one of them at a time by walking over it, and each sheet can only contain one character (you have to write them so large so that aliens from space can see them). A transition function would be like a look-up table you carry in your pocket, which says stuff like “if you’re hungry and the paper you’re on contains a 1, then you become angry, change the 1 to a 0 on your sheet of paper, and move to the right by one sheet of paper.” Moreover, one of the states of the Turing machine is designated the initial state (the state which it starts in every time it’s run), some of the states are designated accepting states, and some of them are designated rejecting states. A Turing machine is completely specified by its states along with the above designations and its transition function. When you think Turing machine, think “theoretical computer.” Turing machines don’t have to be simulated by electronic computers. Anything that can do what a Turing machine does can act like a computer. Instead of electronic circuits acting as logic gates, you can use billiard-balls bouncing inside a box instead. This model has actually been proposed.

Now, every program in your computer acts like a Turing machine, except for one difference: the tape is not infinitely long, i.e., you have a finite amount of work space. For now, let’s only consider programs which answer Yes/No questions. For example, consider a program which decides if a given positive integer is prime. Many graphing calculators, such as the TI-89 graphing calculator, have such a function; on the TI-89, the function is called isPrime(). The calculator doesn’t magically know if a number is prime or not. When you tell it to do isPrime(123), it follows a specific set of instructions, or algorithm, which was programmed into it. The algorithm corresponds to the transition function of the Turing machine. When you tell the calculator or Turing machine to do isPrime(123), it first converts the input, 123, into the language with which it operates, for example, binary numbers. In this case, the Turing machine reads as its input the binary of 123, which is 1111011 and writes that down on the first 7 cells of its tape. Then it faithfully follows its transition function and performs steps and finally halts in either an accepting state or rejecting state. If it ends on an accepting state, it spits out the answer True, and if it ends on a rejecting state, it spits out the answer False. In our case, the machine will end up on a rejecting state, since 123 = 3 x 41.

However, programmers nowadays don’t have to worry about the nitty-gritty details of coming up with an appropriate transition function for a Turing machine that will correctly decide if its input is prime and then putting together an electronic circuit that will simulate the Turing machine. Thankfully, all that hard work has been done decades ago, and now everything’s been abstracted. We can write programs in programming languages like C++ or Java, and the compiler does all the work of translating our code into machine code, which the machine then reads in and performs the necessary steps to simulate the appropriate Turing machine.

Now, how does a computer actually check if a number is prime? That is, what is a sequence of instructions such that, when given a positive integer n, will always output the correct answer as to whether n is prime or not? Often one can write an algorithm by thinking about how one would do it by hand. If you were asked to determine if a number is prime or not, how would you do it? Well, one can directly use the definition of primality. The number n is prime if and only if some integer d > 1 evenly divides n. So, one way would be to start from 2 and check if every number up to n-1 divides n. If none do, then n is prime, otherwise n is not. This may seem like a stupid way to do it, and in some sense it is, but it works and you have to keep in mind that computers crunch numbers a lot faster than humans do. The algorithm just described can be written in Python as follows:

def isPrime(n):
    if n < 2:
        return False
    else:
        for d in range(2, n):
            if n % d == 0:
                return False
        return True

In case you’re not familiar with Python syntax, this is what the code does: it defines a function isPrime(n) which takes n as its input. Then, it first checks if n < 2. If so, then it’ll spit out False, since there are no primes less than 2. If not, then the code goes to the else branch. The for loop basically iteratively sets d to be 2, 3, 4, etc. all the way until n-1. For each value, it’ll test if d divides n. The n % d means taking the remainder when dividing n by d, and == 0 is checking if the result is equal to 0. If this condition is true, then d divides n, so n is not prime, so we return False. Finally, after running through all these values of d, if no divisors were found, then return True.

You may notice that this algorithm takes a linear amount of time in n. That is, if you double n, then the number of divisors the algorithm checks roughly doubles as well. We say that this is an O(n)-time algorithm, where n is the input. Note that we can modify the algorithm so that it only checks divisors d up to \sqrt n. We can do this because if n had a divisor d \ge \sqrt n, then it would have to have a corresponding divisor \frac nd \le \sqrt n. Therefore we could make the algorithm an O(\sqrt n)-time algorithm. Making algorithms more efficient is a huge area of study in computer science, and deserves at least a post on its own.

To recap, you should have learned the following from this post:

  • An intuitive idea of what a Turing machine is, and how modern electronic computers relate to them
  • What an algorithm is
  • The relationship between algorithms and Turing machines
  • An algorithm for determining the primality of positive integers
Advertisements