Turing and computability

Turing Machine
Turing Machine

It all starts with a paper he wrote in 1937: “On computable numbers, with an application to the Entscheidungsproblem.” The paper gave an answer to an important problem which had been haunting mathematicians for years: can there be a “mechanical method which will tell whether any statement of mathematics is true or false?  This “decision problem” (Entscheidungsproblem in German) was one of the key problems set out by David Hilbert in his ambitious program to put maths onto a proper, solid foundation.

The main difficulty with the decision problem is trying to define what we mean by a “mechanical method.” To anyone today, that would automatically bring to mind a computer – but back then, there was no real idea of automatic computation: “computer” was a job description meaning someone who does calculations! Turing’s idea, unlike the complex mathematical constructs of others who worked on the problem in terms of an actual machine, but one which was very simple and could be mathematically reasoned about.

This “Turing machine” is very simple. It consists of a length of tape which has boxes on it within which symbols can be written. A head moves across the tape, reading the symbols and sometimes erasing and replacing them according to the very simple rules – so simple that to do even the most basic tasks can take hundreds of rules.

alan turing statue manchesterEven though the machine is so simple, Turing showed that it could do any simple arithmetical or logical calculation he could imagine given the right program (i.e. the right set of rules.) And since all complex calculations are built out of these simple ones, it could do those too. Now he had his mathematical definintion of a “mechanical method.”

His next step to find a problem it couldn’t solve – something it couldn’t give a true or false answer to. Here again, his genius shows through: his idea was to show that you could, with the right set of rules, make a Turing machine which could be given an encoding of the rules of another Turing machine which it would then emulate. This new machine, the Universal Turing machine, would act exactly like the machine whose description it had been fed. This was a major breakthrough: the idea of programs as just another kind of data. It’s how all computers work now: when we write a program, we describe the rules of  a machine which the computer then emulates.

But this is just a step on the way to his proof. He knew that some Turing machines stop (they go to a special HALT state) and some just go on forever, and that isn’t easy to tell them apart. So he asked, “can you build a Turing machine which can tell if another Turing machine, encoded as data, would ever stop?” he showed that if this were possible, it would create a paradox – so there can be no such machine.

This showed that what can be computed by his machine has limits – and all computers are equivalent to Turing machines, just with a few “bells and whistles” to make them faster and more convenient.

By itself, this proof might seem a little depressing. But in many ways it’s not proof that’s important; other people came up with other proofs at around the same time. What’s important is what came out of his method: a clear idea of what it means to compute; the idea of the algorithm (the mechanical method”) and a mathematical groundwork for computation. He showed that any computer we can imagine building would be equivalent to a Turing machine, and gave us tools to reason about them.

One of the practical outcomes is the idea of complexity theory, which lets us divide tasks into classes depending on how difficult they are. For example, “P” problems can be solved on a Turing machine in a “reasonable” (polynomial) amount of time; while “NP” problems are much harder, although the answer can be verified in a reasonable amount of time. One of the biggest open questions in computer science is whether the two classes, P and NP, might actually turn out to be the same – that is , is there not some trick we’ve missed to turn NP problems into P problems? If that’s true it would completely change the world: all of the world’s codes and ciphers rely on NP problems to make them unbreakable.

Even more practically, Turing’s ideas gave people a real idea of what a practical computer needed; lots of memory, programs made up of only a few simple instructions, and “if…then…” rules. He showed that a computer which was at least as powerful as his Turing machine could compute absolutely anything without having to be specifically built for that task. This inspired the early designers and showed them in which direction to go. And as time goes on, and the complexity of our program increases, we find ourselves using the work more and more.

Finally, Turing’s ideas have found their place in philosophy: are our brains equivalent to Turing machines? Is the entire Universe a Turing machine?

By Jim Finnis

Turing a chyfrifiadwyedd

Cychwynna’r holl beth gyda erthygl a ysgrifennodd yn 1937: “On computable numbers, with an application to the Entscheidungsproblem.” Cyflwynodd yr erthygl ateb i gwestiwn pwysig a oedd wedi peri penbleth i fathemategwyr ers blynyddoedd, sef, a oes dull mecanyddol o ganfod a yw datganiad mathemategol yn wir neu yn anwir? Roedd y broblem benderfynu hon  (Entscheidungsproblem mewn Almaeneg) yn un o’r problemau allweddol a amlinellwyd gan  David Hilbert yn ei raglen uchelgeisiol i roi i fathemateg seiliau cadarn priodol.

Prif anhawster y broblem benderfynu yw ceisio diffinio beth yw ystyr “y dull mecanyddol”. Yn y byd cyfoes, meddyliwn yn syth am gyfrifiadur – ond bryd hynny doedd dim syniad o gyfrifo awtomatig – swydd ddisgrifiad oedd cyfrifiadur i ddisgrifio person a wnâi waith cyfrifo. Syniad Turing, yn annhebyg i’w gyfoedion a ddibynnai ar syniadau mathemategol cymhleth, oedd i feddwl am y broblem yn nhermau peiriant go iawn, ond peiriant syml y gellid rhesymegu yn ei gylch yn fathemategol.

Y mae’r peiriant Turing hwn yn syml iawn. Y cwbl ydyw yw strimyn hir o rhuban y gellid argraffu arno wedi ei rannu yn sgwariau, gyda darllenydd yn darllen y symbolau ac naill ai yn dileu neu yn  eu hargraffu yn ôl gofynion cyfres o reolau syml – rheolau mor syml nes byddai angen cannoedd o reolau i gyflawni hyd yn oed y dasg fwyaf syml.

Er bod y peiriant mor syml, dangosodd Turing y gallai wneud unrhyw gyfrifiad rhifyddegol neu resymegol y gallai ddychmygu petai’r peiriant yn derbyn y rhaglen gywir (h.y. Y set gywir o reolau). A chan fod pob cyfrifiad cymhleth yn seiliedig ar gyfrifon syml, gallai’r peiriant gyflawni’r rheiny hefyd. Nawr, roedd ganddo ei ddiffiniad mathemategol o ddull mecanyddol.

Y cam nesaf oedd i ganfod problem na allai’r peiriant ddatrys – problem na ellid ei ddatrys ar ffurf gwir/anwir. Yma eto, daw dawn Alan Turing i’r amlwg, ei syniad oedd i ddangos y gellid, drwy ddefnyddio’r set gywir o reolau, greu peiriant Turing a fyddai yn gallu derbyn set o reolau ar gyfer peiriant Turing arall, ac felly byddai’r ail beiriant yn gallu efelychu’r cyntaf. Roedd y peiriant newydd hwn, y Peiriant Turing Cyffredinol yn ymddwyn yn union fel y peiriant yr oedd yn ddynwared. Roedd hyn yn gam sylweddol ymlaen: y syniad o raglenni fel math benodol o ddata. Dyma sut mae pob cyfrifiadur yn gweithio; pan ysgrifennwn raglen, rydym yn disgrifio rheolau peiriant, ac mae’r cyfrifiadur yn dynwared y peiriant hwnnw.

Cam fodd bynnag ydoedd hyn tuag at ganfod y prawf angenrheidiol. Deallai fod rhai peiriannau Turing yn stopio (gan fynd i gyflwr AROS arbennig) tra bo eraill yn parhau i redeg am byth. Nid peth hawdd ydyw i’w gwahaniaethu. Felly holodd “a oes modd adeiladu peiriant Turing a fyddai yn gallu penderfynu a fyddai peiriant Turing arall yn stopio?” Petai modd gwneud hynny, byddai’n creu sefyllfa baradocsaidd, ac felly ni allai peiriant o’r fath fyth fodoli.

Dangosodd hyn fod terfynau i’r hyn a ellir ei gyfrifo yn fecanyddol, a chan fod pob cyfrifiadur yn fersiwn mwy soffistigedig o beiriant Turing er mwyn eu galluogi i fod yn gyflymach ac yn fwy cyfleus, dangosodd fod terfynau i bwer cyfrifiaduron.

Ynddo’i hun, efallai fod hyn braidd yn siomedig. Ond ar sawl ystyr, nid y prawf sydd yn bwysig, gan fod eraill, trwy ddulliau gwahanol, wedi canfod yr un peth. Beth sydd yn bwysig yw beth yw oblygiadau’r prawf, sef beth yw ystyr cyfrifo, pwysigrwydd yr algorithm (y dull mecanyddol) a sail mathemategol ar gyfer cyfrifiadura. Dangosodd y byddai unrhyw gyfrifiadur y gallwn ddychmygu  yn gweithredu fel peiriant Turing, a rhoddodd i ni y teclynnau i resymegu yn eu cylch.

Un o’r oblygiadau ymarferol yw theori gymhlethdod, sydd yn ein caniatáu i rannu tasgau i mewn i gategorïau gan ddibynnu ar pa mor anodd ydynt i’w cyflawni. Er enghraifft, gellid datrys problemau P ar beiriant Turing mewn cyfnod rhesymol (h.y. polynomiaidd) o amser, tra bo problemau NP yn anos, er bod modd eu datrys mewn cyfnod rhesymol o amser. Un o’r posau mwyaf sylweddol ar gyfer cyfrifiadurwyr yw a yw’n bosib fod y ddau gategori – P ac NP yn unfath, hynny yw, a oes rhywbeth rydym wedi ei fethu a fyddai’n troi problemau NP i mewn i broblemau P? OS yw hynny’n wir. Byddai’n newid y byd, gan fod yr holl godau a ddefnyddir yn dibynnu ar broblemau NP  er mwyn eu cadw’n ddirgel.

Yn fwy ymarferol fyth, rhoddodd syniadau Turing syniad cliriach i bobol o beth byddai anghenion ymarferol cyfrifiaduron; cof sylweddol, rhaglenni syml a rheolau “os….felly…”. Dangosodd y gallai peiriant gyda’r un gallu a’i beiriant Turing gyfrifo unrhywbeth heb iddo orfod bod wedi ei gynllunio yn benodol ar gyfer y dasg. Ysgogodd hyn gread y gyfrifiaduron cyntaf. A thros amser, fel daw ein rhaglenni yn fwy soffistigedig, dibynnwn yn fwyfwy ar ei waith.

I gloi, mae gwaith Turing wedi ennill ei le mewn athroniaeth; a yw’r ymennydd yn beiriant Turing? A yw’r bydysawd yn beiriant Turing?

Gan Jim Finnis