Network: Alan Turing and his oracle machine - Arts and Entertainment - The Independent

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
Robin Thicke's video for 'Blurred Lines' has been criticised for condoning rape

Robin Thicke admits he didn't write 'Blurred Lines'

music
Arts and Entertainment
While many films were released, few managed to match the success of James Bond blockbuster 'Skyfall'

film
Arts and Entertainment
Matt Damon as Jason Bourne in The Bourne Ultimatum (2007)

film
Arts and Entertainment
Sheridan Smith as Cilla Black

Review: Cilla, ITV TV
Arts and Entertainment

TV
PROMOTED VIDEO
Have you tried new the Independent Digital Edition apps?
Arts and Entertainment
Keira Knightley and Benedict Cumberbatch star in the Alan Turing biopic The Imitation Game

film
Arts and Entertainment
Kanye West is on his 'Yeezus' tour at the moment

Music
Arts and Entertainment
Rob James-Collier, who plays under-butler Thomas Barrow, admitted to suffering sleepless nights over the Series 5 script

TV
Arts and Entertainment
Bradley Cooper and Jennifer Lawrence star in new film 'Serena'

film
Arts and Entertainment
Some might argue that a fleeting moment in the actor’s scintillating, silver-tongued company is worth every penny.

TV
Arts and Entertainment
Colin Firth stars as master magician Stanley Crawford in Woody Allen's 'Magic in the Moonlight'

film
Arts and Entertainment
U2 have released Songs of Innocence in partnership with Apple

musicBand have offered new record for free on iTunes
Arts and Entertainment
Brad Pitt stars in David Ayer's World War II drama Fury

film
Arts and Entertainment
Top hat: Pharrell Williams

music
Arts and Entertainment
Jonah Hill and Channing Tatum star as undercover cops in 22 Jump Street

film
Arts and Entertainment
David Bowie is back with fresh music after last year's hit album The Next Day

music
Arts and Entertainment
Keith Richards is publishing 'Gus and Me: The Story of My Granddad and My First Guitar', a children's book about his introduction to music

music
Arts and Entertainment
Calvin Harris has generated £4m in royalties from the music platform

music
Arts and Entertainment
Jenna Coleman stars as the Time Lord's companion Clara in Doctor Who

TV
Arts and Entertainment
Time and time again: the popular daytime quiz has been a fixture on Channel 4 since 1982

TV
Arts and Entertainment

To mark Tolstoy's 186th birthday

books
Arts and Entertainment
Rachel McAdams is reportedly competing with Mad Men's Elisabeth Moss for a major role in True Detective

TV
Arts and Entertainment
Sam Smith returned to the top spot with his album 'In The Lonely Hour'

music
Arts and Entertainment
Steve Backshall is set to dance with Ola Jordan on Strictly Come Dancing. 'I have a friend who's a dancer and she said to me 'You want Ola because she's a fantastic dancer and she can make anyone look good' meaning 'even you'!' he said.

TV
Arts and Entertainment
Sting and Paul Simon on stage together at Carnegie Hall in New York

music
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.

    Mystery of the Ground Zero wedding photo

    A shot in the dark

    Mystery of the wedding photo from Ground Zero
    His life, the universe and everything

    His life, the universe and everything

    New biography sheds light on comic genius of Douglas Adams
    Save us from small screen superheroes

    Save us from small screen superheroes

    Shows like Agents of S.H.I.E.L.D are little more than marketing tools
    Reach for the skies

    Reach for the skies

    From pools to football pitches, rooftop living is looking up
    These are the 12 best hotel spas in the UK

    12 best hotel spas in the UK

    Some hotels go all out on facilities; others stand out for the sheer quality of treatments
    These Iranian-controlled Shia militias used to specialise in killing American soldiers. Now they are fighting Isis, backed up by US airstrikes

    Widespread fear of Isis is producing strange bedfellows

    Iranian-controlled Shia militias that used to kill American soldiers are now fighting Isis, helped by US airstrikes
    Topshop goes part Athena poster, part last spring Prada

    Topshop goes part Athena poster, part last spring Prada

    Shoppers don't come to Topshop for the unique
    How to make a Lego masterpiece

    How to make a Lego masterpiece

    Toy breaks out of the nursery and heads for the gallery
    Meet the ‘Endies’ – city dwellers who are too poor to have fun

    Meet the ‘Endies’ – city dwellers who are too poor to have fun

    Urbanites are cursed with an acronym pointing to Employed but No Disposable Income or Savings
    Paisley’s decision to make peace with IRA enemies might remind the Arabs of Sadat

    Ian Paisley’s decision to make peace with his IRA enemies

    His Save Ulster from Sodomy campaign would surely have been supported by many a Sunni imam
    'She was a singer, a superstar, an addict, but to me, her mother, she is simply Amy'

    'She was a singer, a superstar, an addict, but to me, her mother, she is simply Amy'

    Exclusive extract from Janis Winehouse's poignant new memoir
    Is this the role to win Cumberbatch an Oscar?

    Is this the role to win Cumberbatch an Oscar?

    The Imitation Game, film review
    England and Roy Hodgson take a joint step towards redemption in Basel

    England and Hodgson take a joint step towards redemption

    Welbeck double puts England on the road to Euro 2016
    Relatives fight over Vivian Maier’s rare photos

    Relatives fight over Vivian Maier’s rare photos

    Pictures removed from public view as courts decide ownership
    ‘Fashion has to be fun. It’s a big business, not a cure for cancer’

    ‘Fashion has to be fun. It’s a big business, not a cure for cancer’

    Donatella Versace at New York Fashion Week