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

Arts and Entertainment

Great British Bake Off
Have you tried new the Independent Digital Edition apps?
Arts and Entertainment

ebooksNow available in paperback
Arts and Entertainment

ebooks
Latest stories from i100
Have you tried new the Independent Digital Edition apps?
SPONSORED FEATURES

ES Rentals

    Independent Dating
    and  

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

    The long walk west: they fled war in Syria, only to get held up in Hungary – now hundreds of refugees have set off on foot for Austria

    They fled war in Syria...

    ...only to get stuck and sidetracked in Hungary
    From The Prisoner to Mad Men, elaborate title sequences are one of the keys to a great TV series

    Title sequences: From The Prisoner to Mad Men

    Elaborate title sequences are one of the keys to a great TV series. But why does the art form have such a chequered history?
    Giorgio Armani Beauty's fabric-inspired foundations: Get back to basics this autumn

    Giorgio Armani Beauty's foundations

    Sumptuous fabrics meet luscious cosmetics for this elegant look
    From stowaways to Operation Stack: Life in a transcontinental lorry cab

    Life from the inside of a trucker's cab

    From stowaways to Operation Stack, it's a challenging time to be a trucker heading to and from the Continent
    Kelis interview: The songwriter and sauce-maker on cooking for Pharrell and crying over potatoes

    Kelis interview

    The singer and sauce-maker on cooking for Pharrell
    Refugee crisis: David Cameron lowered the flag for the dead king of Saudi Arabia - will he do the same honour for little Aylan Kurdi?

    Cameron lowered the flag for the dead king of Saudi Arabia...

    But will he do the same honour for little Aylan Kurdi, asks Robert Fisk
    Our leaders lack courage in this refugee crisis. We are shamed by our European neighbours

    Our leaders lack courage in this refugee crisis. We are shamed by our European neighbours

    Humanity must be at the heart of politics, says Jeremy Corbyn
    Joe Biden's 'tease tour': Could the US Vice-President be testing the water for a presidential run?

    Joe Biden's 'tease tour'

    Could the US Vice-President be testing the water for a presidential run?
    Britain's 24-hour culture: With the 'leisured society' a distant dream we're working longer and less regular hours than ever

    Britain's 24-hour culture

    With the 'leisured society' a distant dream we're working longer and less regular hours than ever
    Diplomacy board game: Treachery is the way to win - which makes it just like the real thing

    The addictive nature of Diplomacy

    Bullying, betrayal, aggression – it may be just a board game, but the family that plays Diplomacy may never look at each other in the same way again
    Lady Chatterley's Lover: Racy underwear for fans of DH Lawrence's equally racy tome

    Fashion: Ooh, Lady Chatterley!

    Take inspiration from DH Lawrence's racy tome with equally racy underwear
    8 best children's clocks

    Tick-tock: 8 best children's clocks

    Whether you’re teaching them to tell the time or putting the finishing touches to a nursery, there’s a ticker for that
    Charlie Austin: Queens Park Rangers striker says ‘If the move is not right, I’m not going’

    Charlie Austin: ‘If the move is not right, I’m not going’

    After hitting 18 goals in the Premier League last season, the QPR striker was the great non-deal of transfer deadline day. But he says he'd preferred another shot at promotion
    Isis profits from destruction of antiquities by selling relics to dealers - and then blowing up the buildings they come from to conceal the evidence of looting

    How Isis profits from destruction of antiquities

    Robert Fisk on the terrorist group's manipulation of the market to increase the price of artefacts
    Labour leadership: Andy Burnham urges Jeremy Corbyn voters to think again in last-minute plea

    'If we lose touch we’ll end up with two decades of the Tories'

    In an exclusive interview, Andy Burnham urges Jeremy Corbyn voters to think again in last-minute plea