Network: Alan Turing and his oracle machine

Hypercomputing might be just around the corner

THE BRITISH computer scientist Alan Turing was truly a remarkable individual. Like a lot of geeks, I've long had an interest in his work. There's a very interesting article about him and some of his lesser-known work in this month's Scientific American by B Jack Copeland and Diane Proudfoot.

Aside from being a principal contributor to cracking the German Enigma code during the Second World War, Turing single-handedly also formulated theories upon which much of modern computer science is built. Turing anticipated precepts of artificial intelligence decades before it became a field of academic pursuit.

Turing postulated a machine, now referred to as the Turing machine, a simple, hypothetical device that could read and be guided by marks on a length of paper tape. Working with paper and pencil, Turing used his creation to form theories that stand to this day.

He showed that there was no absolute way to protect computers from crashing bugs. It's not that the Microsofts and IBMs of this world don't want to stop crashes, it's that they can't. Turing showed that it's impossible to predict whether a given program will quit or run forever.

Give Turing's namesake machine enough tape, and enough time, it could, and could not do, exactly what modern supercomputers can, and can not do. And, while this is all remarkable stuff, Turing, who died at age 41, left unpublished and unheralded work that is even more fascinating.

One of the most fascinating of Turing's lesser-known constructs is that of the "o-machine". An o-machine had a black box that could compute the uncomputable. Positing the o (for oracle) box, Turing could show that theoretically, o machines could solve the unsolvable problems that Turing machines could not.

In short, if o machines are possible, then computing and the world, could quickly be turned on their respective heads.

A computer program consists of a long string of ones and zeroes, and can be viewed as a number. Any string of ones and zeroes is a binary number, and can be represented as an integer.

Now, imagine a memory device of some type that is storing a certain special number. This number is irrational, that is to say, it can be written as an infinite string of digits, and it is binary. It might be written as 01010010110. A very important property is that each individual number represents which programs will terminate, and which will not.

So, if a program were represented by the number 7,687,684,959, one would only have to look at the 7,687,684,959th digit of the special number, and the problem would be solved. A zero might stand for "does not terminate", and a one might mean "terminates".

The "oracle" would simply be the device that performs this task of finding the proper digit. Obviously, if the special number doesn't exist, the oracle wouldn't be able to do its job, and it's far from clear if such a number does or could exist.

It should be noted that Turing never specified the workings of the oracle box, but, neither did he ever specify the workings of the Turing machine. He concentrated on the theoretical plain, leaving later generations to work out the details. In fact, many software Turing machines have been created, including Java applets that run in browsers. The oracle comparator would be a relatively simple software construct.

That computers are ubiquitous shows that the details of building practical Turing machines were relatively straightforward. One begins to wonder if the o machine might be an attainable goal as well.

O machines could perform tasks that Turing called hypercomputing, which could go far beyond the capabilities of extant computers. That the human brain routinely goes far beyond the capabilities of even the most advanced computers, is, in the mind of some, an indication that o machines and hypercomputing are possible.

Modern computers, no matter how powerful, have great difficulty doing tasks like recognising a face, that even a small child can do easily. One could take the view that if a human brain is a naturally occurring instance of an o machine, given its great power, then Turing's special number must exist. If thats all true, then like the Turing machine the only trick remaining is to work out the details.

Hypercomputers are likely to be very difficult to create. We might assume that they're thousands of years in the future, except that we already know that things we expect to take centuries often happen in decades or less. Jules Verne predicted television at the end of the 19th century, saying it would take a thousand years to perfect. It actually took less than 50, and many observers think the pace of invention is much faster at the end of the 20th century than it was at the beginning.

So Turing's hyper-computing might be just around the corner. With it might come greatly enhanced abilities to do things like stock market prediction. But even that might pale in contrast to stopping computer crashes.

cg@gulker.com

PROMOTED VIDEO
Arts and Entertainment
Chocolat author Joanne Harris has spoken about the financial struggles most authors face

books
Arts and Entertainment
A scene from How To Train Your Dragon 2

Review: Imaginative storytelling returns with vigour

film
Have you tried new the Independent Digital Edition apps?
Arts and Entertainment
Josh Hutcherson, Donald Sutherland and Jena Malone in Mockinjay: Part 1

film
Arts and Entertainment

film
Arts and Entertainment
Characters in the new series are based on real people, say its creators, unlike Arya and Clegane the Dog in ‘Game of Thrones’
tv
Arts and Entertainment
A waxwork of Jane Austen has been unveiled at The Jane Austen Centre in Bath

books
Arts and Entertainment
Britney Spears has been caught singing without Auto-Tune

music
Arts and Entertainment
Unless films such as Guardians of the Galaxy, pictured, can buck the trend, this summer could be the first in 13 years that not a single Hollywood blockbuster takes $300m

tv
Arts and Entertainment
Miley Cyrus has her magic LSD brain stolen in this crazy video produced with The Flaming Lips

music
Arts and Entertainment
Gay icons: Sesame Street's Bert (right) and Ernie

tv
Arts and Entertainment
Singer Robin Thicke and actress Paula Patton

music
Arts and Entertainment
The new film will be shot in the same studios as the Harry Potter films

books
Arts and Entertainment
Duncan Bannatyne left school at 15 and was still penniless at 29

Bannatyne leaves Dragon's Den

TV
Arts and Entertainment
The French economist Thomas Piketty wrote that global inequality has worsened

books
Arts and Entertainment
David Tennant and Benedict Cumberbatch

TV
Arts and Entertainment
Ben Affleck plays a despondent Nick Dunne in David Fincher's 'Gone Girl'

film
Arts and Entertainment
Pete Doherty (L) and Carl Barât look at the scene as people begin to be crushed

music
Arts and Entertainment

tv
Arts and Entertainment
Pete Doherty and Caral Barat of The Libertines performs on stage at British Summer Time Festival at Hyde Park

music
Arts and Entertainment
Ariana Grande and Iggy Azalea perform on stage at the Billboard Music Awards 2014

music
Arts and Entertainment

theatre
Arts and Entertainment
Zina Saro-Wiwa

art
Independent
Travel Shop
the manor
Up to 70% off luxury travel
on city breaks Find out more
santorini
Up to 70% off luxury travel
on chic beach resorts Find out more
sardina foodie
Up to 70% off luxury travel
on country retreats Find out more
Have you tried new the Independent Digital Edition apps?

ES Rentals

    Independent Dating
    and  

    By clicking 'Search' you
    are agreeing to our
    Terms of Use.

    A History of the First World War in 100 Moments: Peace without magnanimity - the summit in a railway siding that ended the fighting

    A History of the First World War in 100 Moments

    Peace without magnanimity - the summit in a railway siding that ended the fighting
    Scottish independence: How the Commonwealth Games could swing the vote

    Scottish independence: How the Commonwealth Games could swing the vote

    In the final part of our series, Chris Green arrives in Glasgow - a host city struggling to keep the politics out of its celebration of sport
    Out in the cold: A writer spends a night on the streets and hears the stories of the homeless

    A writer spends a night on the streets

    Rough sleepers - the homeless, the destitute and the drunk - exist in every city. Will Nicoll meets those whose luck has run out
    Striking new stations, high-speed links and (whisper it) better services - the UK's railways are entering a new golden age

    UK's railways are entering a new golden age

    New stations are opening across the country and our railways appear to be entering an era not seen in Britain since the early 1950s
    Conchita Wurst becomes a 'bride' on the Paris catwalk - and proves there is life after Eurovision

    Conchita becomes a 'bride' on Paris catwalk

    Alexander Fury salutes the Eurovision Song Contest winner's latest triumph
    Pétanque World Championship in Marseilles hit by

    Pétanque 'world cup' hit by death threats

    This year's most acrimonious sporting event took place in France, not Brazil. How did pétanque get so passionate?
    Whelks are healthy, versatile and sustainable - so why did we stop eating them in the UK?

    Why did we stop eating whelks?

    Whelks were the Victorian equivalent of the donor kebab and our stocks are abundant. So why do we now export them all to the Far East?
    10 best women's sunglasses

    In the shade: 10 best women's sunglasses

    From luxury bespoke eyewear to fun festival sunnies, we round up the shades to be seen in this summer
    Germany vs Argentina World Cup 2014: Lionel Messi? Javier Mascherano is key for Argentina...

    World Cup final: Messi? Mascherano is key for Argentina...

    No 10 is always centre of attention but Barça team-mate is just as crucial to finalists’ hopes
    Siobhan-Marie O’Connor: Swimmer knows she needs Glasgow joy on road to Rio

    Siobhan-Marie O’Connor: Swimmer needs Glasgow joy on road to Rio

    18-year-old says this month’s Commonwealth Games are a key staging post in her career before time slips away
    The true Gaza back-story that the Israelis aren’t telling this week

    The true Gaza back-story that the Israelis aren’t telling this week

    A future Palestine state will have no borders and be an enclave within Israel, surrounded on all sides by Israeli-held territory, says Robert Fisk
    A History of the First World War in 100 Moments: The German people demand an end to the fighting

    A History of the First World War in 100 Moments

    The German people demand an end to the fighting
    New play by Oscar Wilde's grandson reveals what the Irish wit said at his trials

    New play reveals what Oscar Wilde said at trials

    For a century, what Wilde actually said at his trials was a mystery. But the recent discovery of shorthand notes changed that. Now his grandson Merlin Holland has turned them into a play
    Can scientists save the world's sea life from

    Can scientists save our sea life?

    By the end of the century, the only living things left in our oceans could be plankton and jellyfish. Alex Renton meets the scientists who are trying to turn the tide
    Richard III, Trafalgar Studios, review: Martin Freeman gives highly intelligent performance

    Richard III review

    Martin Freeman’s psychotic monarch is big on mockery but wanting in malice