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
'The Archers' has an audience of about five million
radioA growing number of listeners are voicing their discontent; so loudly that even the BBC's director-general seems worried
Arts and Entertainment
Ready to open the Baftas, rockers Kasabian are also ‘great film fans’
musicExclusive: Rockers promise an explosive opening to the evening
Arts and Entertainment
Henry VIII played by Damien Lewis
tvReview: Scheming queens-in-waiting, tangled lines of succession and men of lowly birth rising to power – sound familiar?
Arts and Entertainment
tv
Arts and Entertainment
Hell, yeah: members of the 369th Infantry arrive back in New York
booksWorld War Z author Max Brooks honours WW1's Harlem Hellfighters in new graphic novel
PROMOTED VIDEO
Arts and Entertainment
Beer as folk: Vincent Franklin and Cyril Nri (centre) in ‘Cucumber’
tvReview: This slice of gay life in Manchester has universal appeal
Arts and Entertainment
‘A Day at the Races’ still stands up well today
film
Have you tried new the Independent Digital Edition apps?
Arts and Entertainment

ebooksNow available in paperback
Arts and Entertainment

ebooks
Arts and Entertainment
‘The Royals’ – a ‘twisted, soapy take on England’s first family’
tvAnd its producers have already announced a second season...
Arts and Entertainment
Kraftwerk performing at the Neue Nationalgalerie (New National Gallery) museum in Berlin earlier this month
musicWhy a bunch of academics consider German electropoppers Kraftwerk worthy of their own symposium
Arts and Entertainment
Icelandic singer Bjork has been forced to release her album early after an online leak

music
Arts and Entertainment
Colin Firth as Harry Hart in Kingsman: The Secret Service

film
Arts and Entertainment
Brian Blessed as King Lear in the Guildford Shakespeare Company's performance of the play

theatre
Arts and Entertainment
In the picture: Anthony LaPaglia and Martin Freeman in 'The Eichmann Show'

tv
Arts and Entertainment
Anne Kirkbride and Bill Roache as Deirdre and Ken Barlow in Coronation Street

tvThe actress has died aged 60
Arts and Entertainment
Marianne Jean-Baptiste defends Joe Miller in Broadchurch series two

tv
Arts and Entertainment
The frill of it all: Hattie Morahan in 'The Changeling'

theatre
Arts and Entertainment
Gillian Anderson and David Duchovny may reunite for The X Files

tv
Arts and Entertainment
Jeremy Clarkson, left, and Richard Hammond upset the locals in South America
TV
News
A young woman punched a police officer after attending a gig by US rapper Snoop Dogg
people
Arts and Entertainment
Reese Witherspoon starring in 'Wild'

It's hard not to warm to Reese Witherspoon's heroismfilm
Arts and Entertainment
Word up: Robbie Coltrane as dictionary guru Doctor Johnson in the classic sitcom Blackadder the Third
books

Arts and Entertainment
The Oscar nominations are due to be announced today

Oscars 2015
Arts and Entertainment
Hacked off: Maisie Williams in ‘Cyberbully’

Maisie Williams single-handedly rises to the challenge

TV
Arts and Entertainment
Eddie Redmayne in The Theory of Everything and Benedict Cumberbatch in The Imitation Game are both nominated at the Bafta Film Awards
Latest stories from i100
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.

    Isis hostage crisis: Militant group stands strong as its numerous enemies fail to find a common plan to defeat it

    Isis stands strong as its numerous enemies fail to find a common plan to defeat it

    The jihadis are being squeezed militarily and economically, but there is no sign of an implosion, says Patrick Cockburn
    Virtual reality thrusts viewers into the frontline of global events - and puts film-goers at the heart of the action

    Virtual reality: Seeing is believing

    Virtual reality thrusts viewers into the frontline of global events - and puts film-goers at the heart of the action
    Homeless Veterans appeal: MP says Coalition ‘not doing enough’

    Homeless Veterans appeal

    MP says Coalition ‘not doing enough’ to help
    Larry David, Steve Coogan and other comedians share stories of depression in new documentary

    Comedians share stories of depression

    The director of the new documentary, Kevin Pollak, tells Jessica Barrett how he got them to talk
    Has The Archers lost the plot with it's spicy storylines?

    Has The Archers lost the plot?

    A growing number of listeners are voicing their discontent over the rural soap's spicy storylines; so loudly that even the BBC's director-general seems worried, says Simon Kelner
    English Heritage adds 14 post-war office buildings to its protected lists

    14 office buildings added to protected lists

    Christopher Beanland explores the underrated appeal of these palaces of pen-pushing
    Human skull discovery in Israel proves humans lived side-by-side with Neanderthals

    Human skull discovery in Israel proves humans lived side-by-side with Neanderthals

    Scientists unearthed the cranial fragments from Manot Cave in West Galilee
    World War Z author Max Brooks honours WW1's Harlem Hellfighters in new graphic novel

    Max Brooks honours Harlem Hellfighters

    The author talks about race, legacy and his Will Smith film option to Tim Walker
    Why the league system no longer measures up

    League system no longer measures up

    Jon Coles, former head of standards at the Department of Education, used to be in charge of school performance rankings. He explains how he would reform the system
    Valentine's Day cards: 5 best online card shops

    Don't leave it to the petrol station: The best online card shops for Valentine's Day

    Can't find a card you like on the high street? Try one of these sites for individual, personalised options, whatever your taste
    Diego Costa: Devil in blue who upsets defences is a reminder of what Liverpool have lost

    Devil in blue Costa is a reminder of what Liverpool have lost

    The Reds are desperately missing Luis Suarez, says Ian Herbert
    Ashley Giles: 'I'll watch England – but not as a fan'

    Ashley Giles: 'I'll watch England – but not as a fan'

    Former one-day coach says he will ‘observe’ their World Cup games – but ‘won’t be jumping up and down’
    Greece elections: In times like these, the EU has far more dangerous adversaries than Syriza

    Greece elections

    In times like these, the EU has far more dangerous adversaries than Syriza, says Patrick Cockburn
    Holocaust Memorial Day: Nazi victims remembered as spectre of prejudice reappears

    Holocaust Memorial Day

    Nazi victims remembered as spectre of prejudice reappears over Europe
    Fortitude and the Arctic attraction: Our fascination with the last great wilderness

    Magnetic north

    The Arctic has always exerted a pull, from Greek myth to new thriller Fortitude. Gerard Gilbert considers what's behind our fascination with the last great wilderness