Abstractions of Computation, the Church-Turing Hypothesis, and the Halting Problem

Author: Philip Wu

NOTE FOR READER: This is the first post in a (hopefully) multi-post project exploring interesting topics in computer science, physics, and mathematics.

Your calculator is a wonderful thing.

It can calculate any logically computable numerical expression you give it and almost instantly return the correct value to you. You can give it arithmetic problems ranging from an incredibly simple addition problem all the way to an incredibly complicated bundle of logarithms, trigonometric functions, matrices, and much, much more, to algebraic problems that calculates the integral and derivatives of a function, and it will simply regurgitate the answer onto the display.

What if I told you that you, with an infinite amount of erasers and lead and time, an infinite tape, the ability to only move your pencil one square to the right or to the left, and a mentality incapable of going insane, can do the same thing? For you guys who love computer science, this shouldn’t be a surprise. You would know, it’s a Turing Machine!

Specifically, a Turing Machine is an abstraction of computation by the granddaddy of computer science, Alan Turing, in which an algorithm of various states takes in a tape of squares that can have one or no object from a finite alphabet written on them (although just only using 0s and 1s is enough to do all problems any Turing Machine can do) and can do the following things with the tape:

1. Check a square’s value.

2. Edit the square’s value.

3. Shift the tape one square to the left or right.

4. Change states

5. Accept

6. Reject

7. Halt

Here is an example of a simple Turing Machine algorithm that removes all the 1s from a given tape consisting of a string of consecutive 0s and 1s with the rest of the tape being blank. We start at the first non-blank square

With Turing Machines you can create functions as simple as addition, incrementation, and other basic arithmetic operators to applications as complicated as solving for differential equations and conducting machine learning.

Before we continue, if you wish, here are some functions that you can try to create a Turing Machine for:

1. An increment function.

2. An unary addition function, in which you are given two unary inputs that are separated by one space.

3. A binary addition function, in which you are given two binary inputs that are separated by one space with the largest binary bit of each input being 1 and the machine starts on the second input’s last digit. Assume the first input is larger than the second input. For this you can define your own alphabet, so you don’t have to use only 0s, 1s and _s. However, you can definitely do it with only 0s, 1s, and _s, but I couldn’t figure that one out (RIP).

4. A greater than function that accepts two binary inputs separated by one space. It accepts the tape if the first input is larger than the second one and rejects it otherwise.

5. A function that checks a binary number to see if its a palindrome and accepts if and rejects if not.

Click here for the solutions (your’s might vary):

Lambda Calculus

Another way you can define computation is through Lambda Calculus. It is much more “mathematical” than the Turing Machine, with its tangible and simple components of tapes, but is also incredibly easy to understand and offers a different viewpoint on computation.

Lambda Calculus was invented by Alonzo Church, a mentor of Alan Turing, before the Turing Machine. Like the Turing Machine, it is very simple, with only three symbols:

1. Letters that represent variables

3. Parentheses, which serve their usual function.

Now that you know how Lambda Calculus works, let’s derive some numerical operators.

First we must define numbers. For this, we use Church Numerals, which follow as:

Now let’s try to come up with some lambda expressions for various basic arithmetic operators. See if you can do them yourself. Solutions will be in the link from Turing Machines.

INCREMENT: Take one Church Numeral and return it incremented.

ADDITION: Take two Church Numerals and return their sum.

MULTIPLICATION: Take two Church Numerals and return their product.

Now let’s derive some logic functions.

See if you can derive the AND function and the OR function. For solutions, refer to the link for solutions on the Turing Machines.

Just like with Turing Machines, with a lot of definitions, you can create Lambda Expressions complicated enough to solve differential equations and carry out machine learning. It turns out, in fact, that Lambda Expressions and Turing Machines are both powerful enough, they can theoretically compute the same amount of problems, as the computer or phone or whatever device you are reading this with. More accurately, it is better to say that the best computer with finite memory we create will be only as powerful as Turing Machines and Lambda Expressions. This is the Church-Turing Hypothesis. Note, it is a hypothesis. It cannot be proved true. It can be falsified, but that is extremely, extremely unlikely. For all practical purposes, however, it is true.

BEFORE YOU CONTINUE:

So, you might ask yourself, what can a Turing Machine or a computer not do in the theoretical realm? We said that a computer can do anything a Turing Machine can do, but that does not mean it can do everything. Can you come up with a logically incomputable algorithm?

Suppose there is an algorithm that takes another algorithm and an input for that other algorithm and then returns yes if that algorithm halts eventually and returns no it if it doesn't halt. For example, if you gave it an algorithm that calculates arithmetical expressions and returns them in exact decimal form and pi it would return no, as pi is irrational. Now, extend those outputs into two more machines, one that takes only yes as an input and then loops forever, and another that takes only no as an input and then halts. What happens when you feed that algorithm itself?

If our algorithm does halt, the first part of the algorithm will give a yes, which will then make the program loop forever, which contradicts our first assumption. Likewise, if our algorithm doesn’t halt, then the first part will give a no and then the second part will halt the algorithm, which contradicts our first assumption. This is the Halting Problem, and there is no theoretical machine that can theoretically solve it.

In the practical realm, there are also many, many problems that computers cannot practically solve, or at least probably can’t. In fact, there are many, many, many more problems that computers cannot practically solve compared to ones computers can solve. This topic, the P vs NP problem, will potentially be explored as another topic.