Unit 4 — Area of Study 3 (From the Study Design)
On completion of this unit the student should be able to explain the scope of algorithmics as an approach to computational problem solving and the universality of computation, and its limits, using core concepts from theoretical computer science.

Hilbert’s Program

In the 1920’s, David Hilbert was trying to show that all of mathematics could be formalised as a finite set of axioms. Hilbert wanted this formal system of maths to be consistent (meaning that it could have no paradoxes), complete (every true statement would be provable), and decidable (meaning that we could tell whether a statement is provable). This is known as Hilbert’s Program.

Gödel’s Incompleteness Theorem

In response to Hilbert’s program, Kurt Gödel published his incompleteness theorem which actually consisted of two parts:

  • If arithemtic is consistent, then there can always be true statements about it that cannot be proven using a finite set of axioms.

  • It is not possible for any proof based upon the set of axioms to demonstrate the consistency of the axioms.

There is a great Veritasium video that goes into depth about what exactly Gödel’s theory was.

Turing Machines

A Turing Machine is one that reads an changes a tape of data according to a prewritten set of rules. The two basic components are the head and the tape. Whilst a turing machines are very basic in terms of their composition, they can tell us a lot about computability.

Alan Turing created Turing machines when he was trying to determine what it meant for something to be computable. Turing said that in order for something to be computable, it needs to have an effective process that can solve the problem. He defined an effective process as:

  • Be able to be done with a pencil and paper.

  • Must contain only a finite number of instructions.

  • Must be able to be done mechanically without insight or ingenuity from a human.

  • Will work without making any errors or mistakes.

  • Produces the final result in a finite number of steps.

Any effective process can be done on a Turing machine. The tape of the turing machine is inifite in length and is divided into cells that are either blank or contain a symbol from a finite set of symbols. The head of the machine can:

  • Move left or right along the tape.

  • Read symbols from the tape.

  • Write symbols to the tape (including replacing them)

The instructions provided to the machine consist of a graph of states, including a starting node and a stopping node. An online demo of a turing machine can be found at https://turingmachine.io

Busy Beavers

The busy beaver game is a challenge for a Turing machine. Basically, the busy beaver game starts with a tape consisting of only zero. The object is to then try and generate as many ones on the tape before terminating (the program has to end).

The number of states that the Turing machine uses will change the number of ones that can be generated. Have a look on Wikipeda to see the current known maximum values of the busy beaver game for different numbers of states in the Turing machine.

One of the big problems with programs written for the busy beaver game is that we often don’t know whether the program will end or not. And there is unfortunately no way to determine whethere any given program will stop or continue forever.

The Church-Turing Thesis

Both Alan Turing and Alonzo Church were trying to describe the concept of computability. Turing via his machines, and Church by this thing called Lambda Calculus (which is outside the scope of this course). Eventually they both realised that they were trying to describe the same thing. Namely that every effective procedure can be computed by a Turing machine.

Basically the Church-Turing thesis says that a Turing machine can compute any problem that is computable. Meaning that for every solvable decision problem, it can be transformed into an equivalent Turing machine problem [Sudkamp1997]. This also means that, if a problem can be solved by a Turing machine, then it would be considered computable.

In formal terms, the Church-Turing thesis looks like [Sudkamp1997]:

There is an effective procedure to solve a decision problem if, and only if, there is a Turing machine that halts for all input strings and solves the problem.

And the extended Church-Turing thesis:

A decision problem \(P\) is partially solvable if, and only if, there is a Turing machine that accepts precisely the elements of \(P\) whose answer is yes.

Cobham’s Thesis

Alan Cobham came up with another way to define whether or not something could be considered computable. He said that, for something to be feasibly computable, it would have to be computable in polynomial time.

This obviously has some limitations as a functional model of computability, as functions with \(\O(n^{100})\) would be considered computable, but \(\O(2^{0.0000001 n})\) would not, even though the second one would be far more practical for large values of \(n\) than the first one.

The Halting Problem

The halting problem is Turing’s answer to Hilbert’s program, and proved that not everything can be computed (which is a bit sad). It consisted of a new kind of Turing machine: the universal Turing machine, which would take as input some data tape, and the program of a different Turing machine. Meaning that the universal Turing machine could run any other turing machine program. And, by the Church-Turing thesis, can compute anything that can be computed.

Turing wanted to answer Hilbert’s question "Is it possible to determine whether any given statement is true or false?". Turing proved that it was impossible.

He first created a universal Turing machine \(H\) that would return true if the given program and data halted, or false if it didn’t. He then attached on another Turing machine \(O\) to the end of \(H\), that would do the opposite of what it recieved (halt if it got true from \(H\), and loop forever if \(H\) returned false). This combination program was then called \(H*\).

Turing then asked what would happen if we gave \(H*\) the input being itself. Well, if \(H*\) halted, then it should just keep going on forever. But if it keeps going on forever then it should halt. This is a contradiction and as such \(H\) cannot exist.

We cannot determine whether a program will halt or not.

As an aside, Turing represented a Turing machine’s program as a real number. He then showed that there were a countable number of computable program numbers. Meaning that there are infinite uncomputable program numbers. This basically means that there are infinite problems that cannot be solved.

DNA Computing

In DNA Computing, components of a specific problem are encoded as physical DNA sequences. Loads of these sequences are then combinedin a lab and mixed up, creating longer sequences that represent all possible solutions. The best out of these solutions can then be filtered out [Adleman1998].

DNA Computing basically allows for massively parallel computing, as when all the different sequences are mixed, they will (probably) try all possible combinations. Meaning that, in theory, DNA computing can be used to overcome some of the limits of computation.

This works well for small samples, but can quickly become infeasible with larger inputs. This is because the amount of DNA required tends to increase exponentially with the input size.

The Chinese Room

John Searle proposed the chinese room argument in response to Turing’s Turing Test. The test was to determine whether an AI could be considered intelligent. Imagine you have two fully enclosed rooms, one with an AI and one with a person, but you don’t know which room has which in it. Then ask the same question to both, and try to determine which response was from the human. If the AI tricks you more than 50% of the time, then Turing said it could be considered "intelligent".

Most computer scientists nowadays believe that, while the Turing test is an interesting though experiment, is not really a useful test for artificial intelligence. One argument against the use of the Turing test is the Chinese Room Argument, and it looks something like the following.

Imagine a native English speaker — who knows no Chinese — is stuck in a room full of boxes containing different Chinese characters, and a book of instructions. This book of instructions essentially acts as the program and allows the person in the room to respond correctly to any given input of Chinese, in Chinese.

As an example, if the person in the room was asked "一周有多少天？", they would simply have to look up in the book of instructions the question, and could then return the appropriate response.

\[\text{一周有多少天？} \longrightarrow \text{七}\]

If the instruction book contained every possible input, then the person in the room could pass the Turing test for understanding Chinese, despite not understanding any Chinese. And should this kind of program really be considered intelligent?

Searle’s chinese room argument is basically about determining the level of an artificial intelligence. With strong AI actually understanding what it is doing, whereas weak AI would just be following rules like the instruction book and not needing to understand what’s going.

Arguments Against

There are a number of responses against the conclusion that Searle made, but here are a few:

The Systems Reply

The systems reply argues that it is the whole system of the room that understands Chinese, even though the person only understands English. This is akin to saying that an individual neuron in your brain doesn’t understand English, but the combination of neurons working together can understand it.

The Brain Simulator Reply

The brain simulator reply argues that if the room were able to simulate all the neurons of a person that speaks Chinese fluently, then it would be not significantly different from having someone who understands Chinese respond. That is, the room would itself simulate the brain of a fluent Chinese speaker.

Neural Networks

A neural network is a computer system often used in artificial intelligence programming that is based on the way that our brains work. They genenerally consist of a bunch of nodes networked together such that an input in to one node propagates out to the output node. For the purposes of VCE Algorithmics, you can think of a neural network as a black box (in reality neural networks consist of a whole bunch of differential equations).

The black box model represents a neural network as consisting of an input layer of a bunch of nodes, the middle "black box", and the output layer.

an input layer of four nodes going into a black box
Figure 1. A diagram of the black box model.

Neural networks undergo a process called machine learning whereby they are trained on some known data set, and the weights of each of the nodes in the hidden layer inside the box are adjusted to provide a better result. It is important to note that training data for a neural network needs to be carefully selected to avoid bias in the dataset (most English language data comes from emails between Enron employees)

Using a neural network is quite difficult to write down on paper, as it doesn’t really follow the same line-by-line nature of the other algorithmic patterns we’ve explored throughout this course.

References