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.

Arts and Entertainment
Secrets of JK Rowling's Harry Potter workings have been revealed in a new bibliography
arts + ents
Arts and Entertainment
Fearne Cotton is leaving Radio 1 after a decade
radio The popular DJ is leaving for 'family and new adventures'
Arts and Entertainment
arts + ents
Arts and Entertainment
Public Service Broadcasting are going it alone
Arts and Entertainment
Eddie Redmayne as transgender artist Lili Elbe in The Danish Girl

First look at Oscar winner as transgender artistfilm
Arts and Entertainment

Oscars 2015 Mexican filmmaker uses speech to urge 'respect' for immigrants

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

Oscars 2015 Bringing you all the news from the 87th Academy Awards

Have you tried new the Independent Digital Edition apps?
Arts and Entertainment

ebooksNow available in paperback
Arts and Entertainment

Arts and Entertainment
Lloyd-Hughes takes the leading role as Ralph Whelan in Channel 4's epic new 10-part drama, Indian Summers

TV Review

The intrigue deepens as we delve further but don't expect any answers just yet
Arts and Entertainment
Jason Segal and Cameron Diaz star in Sex Tape

Razzies 2015 Golden Raspberry Awards 'honours' Cameron Diaz and Kirk Cameron

Arts and Entertainment
The Oscars ceremony 2015 will take place at the Dolby Theatre in Los Angeles
Oscars 2015A quiz to whet your appetite for tonight’s 87th Academy Awards
Arts and Entertainment
Sigourney Weaver, as Ripley, in Alien; critics have branded the naming of action movie network Movies4Men as “offensive” and “demographic box-ticking gone mad”.
TVNaming of action movie network Movies4Men sparks outrage
Arts and Entertainment
Sleater Kinney perform at the 6 Music Festival at the O2 Academy, Newcastle
musicReview: 6 Music Festival
Arts and Entertainment
Sleater Kinney perform at the 6 Music Festival at the O2 Academy, Newcastle
musicReview: 6 Music Festival
Kristen Stewart reacts after receiving the Best Actress in a Supporting Role award for her role in 'Sils Maria' at the 40th annual Cesar awards
A lost Sherlock Holmes story has been unearthed
arts + ents Walter Elliot, an 80-year-old historian, found it in his attic,
Arts and Entertainment
Margot Robbie rose to fame starring alongside Leonardo DiCaprio in The Wolf of Wall Street

Film Hollywood's new leading lady talks about her Ramsay Street days

Arts and Entertainment
Right note: Sam Haywood with Simon Usborne page turning
musicSimon Usborne discovers it is under threat from the accursed iPad
Arts and Entertainment
A life-size sculpture by Nick Reynolds depicting singer Pete Doherty on a crucifix hangs in St Marylebone church
arts + ents
Arts and Entertainment
Escalating tension: Tang Wei and Chris Hemsworth in ‘Blackhat’
filmReview: Chris Hemsworth stars as a convicted hacker in Blackhat
Arts and Entertainment

Oscar voter speaks out

Arts and Entertainment
The Oscars race for Best Picture will be the battle between Boyhood and Birdman

Arts and Entertainment
Anne Boleyn (Claire Foy), Thomas Cromwell (Mark Rylance)
tvReview: Wolf Hall
Arts and Entertainment
Tom Meighan of Kasabian collects the Best Album Award
Arts and Entertainment
Best supporting stylist: the late L’Wren Scott dressed Nicole Kidman in 1997
Arts and Entertainment
Dakota Johnson and Jamie Dornan as Anastasia Steele and Christian Grey in Fifty Shades of Grey


Arts and Entertainment
Mick Carter (Danny Dyer) and Peggy Mitchell (Barbara Windsor)
tv occurred in the crucial final scene
Arts and Entertainment
Glasgow wanted to demolish its Red Road flats last year
Latest stories from i100
Have you tried new the Independent Digital Edition apps?

ES Rentals

    Independent Dating

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

    HIV pill: Scientists hail discovery of 'game-changer' that cuts the risk of infection among gay men by 86%

    Scientists hail daily pill that protects against HIV infection

    Breakthrough in battle against global scourge – but will the NHS pay for it?
    How we must adjust our lifestyles to nature: Welcome to the 'Anthropocene', the human epoch

    Time to play God

    Welcome to the 'Anthropocene', the human epoch where we may need to redefine nature itself
    MacGyver returns, but with a difference: Handyman hero of classic 1980s TV series to be recast as a woman

    MacGyver returns, but with a difference

    Handyman hero of classic 1980s TV series to be recast as a woman
    Tunnel renaissance: Why cities are hiding roads down in the ground

    Tunnel renaissance

    Why cities are hiding roads underground
    'Backstreet Boys - Show 'Em What You're Made Of': An affectionate look at five middle-aged men

    Boys to men

    The Backstreet Boys might be middle-aged, married and have dodgy knees, but a heartfelt documentary reveals they’re not going gently into pop’s good night
    Crufts 2015: Should foreign dogs be allowed to compete?

    Crufts 2015

    Should foreign dogs be allowed to compete?
    10 best projectors

    How to make your home cinema more cinematic: 10 best projectors

    Want to recreate the big-screen experience in your sitting room? IndyBest sizes up gadgets to form your film-watching
    Manchester City 1 Barcelona 2 player ratings: Luis Suarez? Lionel Messi? Joe Hart? Who was the star man?

    Manchester City vs Barcelona player ratings

    Luis Suarez? Lionel Messi? Joe Hart? Who was the star man at the Etihad?
    Arsenal vs Monaco: Monaco - the making of Gunners' manager Arsene Wenger

    Monaco: the making of Wenger

    Jack Pitt-Brooke speaks to former players and learns the Frenchman’s man-management has always been one of his best skills
    Cricket World Cup 2015: Chris Gayle - the West Indies' enigma lives up to his reputation

    Chris Gayle: The West Indies' enigma

    Some said the game's eternal rebel was washed up. As ever, he proved he writes the scripts by producing a blistering World Cup innings
    In Ukraine a dark world of hybrid warfare and murky loyalties prevails

    In Ukraine a dark world of hybrid warfare

    This war in the shadows has been going on since the fall of Mr Yanukovych
    'Birdman' and 'Bullets Over Broadway': Homage or plagiarism?

    Homage or plagiarism?

    'Birdman' shares much DNA with Woody Allen's 'Bullets Over Broadway'
    Broadchurch ends as damp squib not even David Tennant can revive

    A damp squib not even David Tennant can revive

    Broadchurch, Series 2 finale, review
    A Koi carp breeding pond, wall-mounted iPads and a bathroom with a 'wellness' shower: inside the mansion of Germany's 'Bishop of Bling'

    Inside the mansion of Germany's 'Bishop of Bling'

    A Koi carp breeding pond, wall-mounted iPads and a bathroom with a 'wellness' shower