Turing-machine: de grenzen van berekenbaarheid

Lang leve Turing

2012 is uitgeroepen tot het Turing-jaar. Op 23 juni is het precies honderd jaar geleden dat Alan Turing werd geboren. Deze Britse wiskundige en computerwetenschapper is om drie redenen beroemd. Ten eerste bedacht hij de Turing-test, een beroemd gedachte-experiment in de kunstmatige intelligentie. Daarbij wordt een computer geacht intelligent te zijn als een intelligent mens in een conversatie het onderscheid tussen deze computer en een ander mens niet meer kan maken. Ten tweede was Turing in de Tweede Wereldoorlog uiterst belangrijk bij het kraken van versleutelde berichten van de nazi's. De Duitsers codeerden hun berichten met de Enigma-systemen, een combinatie van typemachine en codeermachine, en Turing legde de basis voor het ontcijferen van deze berichten.

Tot slot is hij de bedenker van het onderwerp van dit artikel: de Turing-machine. Dat is een computermodel dat vooral in de theoretische informatica wordt gebruikt om de kracht van computersystemen en de complexiteit van problemen te bestuderen.

Het Centrum Wiskunde & Informatica organiseert voor de gelegenheid een tentoonstelling. Daar is onder andere een echte Enigma-machine te zien, maar ook een werkend Lego-model van een Turing-machine die door Jeroen van den Bos en Davy Landman, wetenschappers van het CWI, is gebouwd.

Helaas!
De video die je probeert te bekijken is niet langer beschikbaar op Tweakers.net.

Video van een Turing-machine die door Jeroen van den Bos en Davy Landman, wetenschappers van het CWI, is gebouwd. © CWI

Deterministische Turing-machine

Hoewel Turing-machines al meer dan driekwart eeuw geleden zijn bedacht, zijn ze nog steeds van groot belang voor de complexiteitstheorie. Informatici gebruiken deze conceptuele computers om te bestuderen of bepaalde problemen redelijkerwijs met behulp van computers kunnen worden opgelost. Omdat ze worden gebruikt om bewijzen te construeren, leunen deze modellen zwaar op wiskundige theorie. Desondanks hebben de uitkomsten van deze onderzoeken grote praktische consequenties, onder meer voor gegevensbeveiliging.

De eenvoudigste Turing-machine is de Deterministische Turing-machine. Deze wordt doorgaans voorgesteld als een rekeneenheid met een lees/schrijf-kop en een tape die zich naar beide kanten oneindig uitstrekt. Op de tape staat de input voor de machine, en afhankelijk van het karakter onder de leeskop wordt een nieuw karakter op de tape geschreven en wordt de kop naar links of rechts verplaatst.

Finite state machine voorbeeld (Wikipedia) De rekeneenheid bevat het programma, niet gedefinieerd in een programmeertaal zoals wij die kennen, maar in de vorm van een Finite-State Machine. Deze kan zich in een aantal states of toestanden bevinden en kan van de ene naar de andere state overgaan; dat heet een transitie.

Voor software-ontwikkelaars is dit een ongebruikelijke manier om een programma te definiëren, maar hardware-ontwikkelaars werken veel aan de hand van dit model. Het is ook mogelijk om een voorzichtige vergelijking tussen de deterministische Turing-machine en een processor te maken. De state wordt dan bepaald door alle processorregisters en de overgangen zijn vastgelegd in de microcode van de cpu, waarin wordt bepaald hoe de registers worden beïnvloed als een machinetaal-instructie wordt uitgevoerd.

We moeten wel bedenken dat deze deterministische Turing-machine niet bedoeld is om een computer of processor te modelleren, maar om iets te kunnen zeggen over de oplosbaarheid van problemen.

P =? NP

In de theoretische informatica noemen we een probleem oplosbaar als we voor een deterministische Turing-machine een algoritme - een finite state machine dus - kunnen verzinnen, dat eindig is voor alle mogelijke input strings op de tape. De laatste state van onze finite state machine is het antwoord voor de betreffende input-string, maar er kan tijdens het uitvoeren van het algoritme ook nog output naar de tape worden geschreven.

Daarmee zijn we aanbeland bij een van de belangrijkste kwesties in de complexiteitstheorie. Problemen waarvoor een algoritme gevonden kan worden dat in redelijke tijd kan worden uitgevoerd, zitten in de complexiteitsklasse P. De maximaal benodigde rekentijd kan dan aan de hand van de lengte van de invoerstring worden bepaald met een polynoomfunctie.

Problemen waarvoor nog geen efficiënt algoritme is gevonden, zitten in de NP-klasse. Deze Niet-deterministisch Polynomiale problemen zijn alleen op te lossen met algoritmen waarvan de rekentijd sneller dan polynomiaal toeneemt als de invoerstring langer wordt. Dat betekent dat de rekentijd voor langere invoerstrings al snel onwerkbaar groot wordt.

Is er voor een probleem helemaal geen algoritme te vinden, dan heet dat probleem onbeslisbaar. Het bekendste onbeslisbare probleem is het Halting-probleem: er is geen algoritme te bedenken dat kan vaststellen of een algoritme - of een Turing-machine - aan de hand van een eindige invoer ook daadwerkelijk een antwoord zal geven. Dit probleem staat model voor een hele zwik onbeslisbare problemen. Voor de wiskundeliefhebbers: volgens het theorema van Rice is het bepalen van een algoritme een onbeslisbaar probleem voor elke partiële functie met niet-triviale eigenschappen. Dat heeft enorme consequenties voor programmeertools die proberen de correctheid of de eindigheid van programma's aan te tonen.

NP-Compleet

Dat voor een willekeurig NP-probleem nog geen polynomiaal algoritme is gevonden, wil nog niet zeggen dat een dergelijk algoritme niet bestaat. Het zou dus kunnen dat er alsnog een efficiënt algoritme voor zo'n NP-probleem wordt verzonnen. Sterker nog, van een aantal NP-problemen is bewezen dat als daar een P-algoritme voor kan worden gevonden, dat dan voor álle NP-problemen een dergelijk algoritme bestaat. Deze klasse van de moeilijkste problemen binnen het NP-domein heet NP-Compleet.

De vraag of uiteindelijk voor alle problemen in de klasse NP een polynomiaal algoritme kan worden gevonden, waarmee die problemen dus in de klasse P terecht komen, wordt door de theoretici P =? NP genoemd. Het vermoeden is echter dat er problemen zijn waarvoor helemaal geen P-algoritme kan bestaan, maar dat bewijzen is vers twee. Dit is niet voor niets een van de zeven Millennium-vraagstukken, waar een geldprijs van een miljoen dollar aan is verbonden.

Bovendien lijken er problemen te zijn die wel in NP zitten maar niet in P of NP-Compleet. Omdat dat laatste betekent dat ze niet kunnen worden gereduceerd naar een NP-Compleet probleem, zijn deze zogenaamde open problemen weer anders van aard dan de problemen in P en NP-Compleet.

P np np-complete np-hard (Wikipedia)

Meer Turing-machines

Niet-Deterministische Turing Machine

Interessant aan NP-problemen is dat antwoorden weliswaar moeilijk te vinden zijn, maar dat eenmaal gegeven oplossingen wel makkelijk te verifiëren zijn. Een bekend NP-Compleet probleem is bijvoorbeeld het Traveling Salesman Problem. Daarbij moet een handelsreiziger alle steden op een lijst bezoeken. Het vinden van een route met een bepaalde maximale lengte blijkt heel snel moeilijker te worden naarmate het aantal steden op de lijst toeneemt. Voor een eenmaal gegeven route is het echter heel makkelijk om te controleren of deze inderdaad korter dan de gevraagde afstand is - daarvoor hoef je immers alleen maar de onderlinge afstanden op te tellen.

Voor deze zogenaamde beslissingsproblemen is de Niet-Deterministische Turing Machine bedacht. Deze bevat een gokmodule die vooraf een mogelijke oplossing op de tape zet. Het verifiëren van dit antwoord kan dan inderdaad in polynomiale tijd gebeuren. Een alternatieve uitwerking bevat geen gokmodule maar geeft de rekeneenheid van de NDTM de mogelijkheid om meerdere transities tegelijk uit te voeren - vandaar de naam 'non-deterministisch'.

AO Scan NDTM
In de praktijk bestaat er natuurlijk geen gokmodule die in een polynomiale tijdspanne een goede oplossing kan leveren - anders was het een P-probleem geweest dat we met een deterministische Turing-machine hadden kunnen oplossen. Enerzijds benadrukt dit nog eens het theoretische karakter van de Turing-machines. Anderzijds brengen quantumcomputers de oplossing voor dit soort berekeningen wel dichterbij. Helaas wordt er vermoed dat NP-Complete problemen ook met quantummachines niet in polynomiale tijd opgelost kunnen worden.

Universal Turing Machine

Er zijn nog diverse andere Turing-machines. De Universele Turing Machine bijvoorbeeld is een systeem dat andere Turing-machines kan simuleren. Behalve de invoer staat dan ook een beschrijving van de te simuleren machine op de tape. Daarmee komt dit model in de buurt van de Von Neumann-architectuur, waarbij het algoritme hetzelfde geheugen gebruikt als de input en output.

Van de verschillende manieren om de berekenbaarheid van problemen te modelleren, is de Turing-machine de meest gebruikte. Twee andere zijn de lamdba-calculus en recursie. Volgens de Church-Turing-thesis maakt het ook niet uit hoe je complexiteit modelleert: elk effectief algoritme kan met alle drie modellen worden beschreven. Anders gezegd: de drie methoden zijn Turing-equivalent.

De praktijk

Dat de methoden om berekenbaarheid te bepalen Turing-equivalent zijn, wil natuurlijk nog niet zeggen dat alle talen en systemen even snel zijn: deze theoretische complexiteitsmodellen zijn niet zomaar naar de praktijk te vertalen. Cobham's these stelt wel dat alleen problemen in P in redelijke tijd kunnen worden opgelost, maar ook polynomiale tijd kan heel lang duren.

Zo zegt het tijd-hiërarchie-theorema dat P bestaat uit een hiërarchie van problemen die steeds moeilijker op te lossen zijn. Dat wil zeggen dat een DTM steeds meer tijd nodig heeft om het antwoord uit te rekenen, bijvoorbeeld omdat de verwerkingstijd kwadratisch in plaats van lineair is ten opzichte van de lengte van de inputstring. De consequentie daarvan is dat er ook P-problemen zijn die oneindig veel polynomiale tijd kosten om op te lossen. Hetzelfde geldt voor de structuur van NP.

Het ruimte-hiërarchie theorema zegt iets vergelijkbaars voor de beschikbare geheugenruimte (de tape): je kunt steeds complexere problemen oplossen naarmate je meer geheugenruimte tot je beschikking hebt. Dat is uitermate relevant als je bedenkt dat de beschikbaarheid van een oneindig lange tape het belangrijkste onderscheid is tussen een Turing-machine en een echte computer.

Aan de andere kant zijn er een heleboel algoritmen bekend die misschien niet de exacte oplossing van een niet-polynomiaal probleem geven, maar wel een goede benadering kunnen leveren.

Parallelle systemen

De complexiteitshiërarchie van P en NP is maar het topje van de ijsberg. De theoretici hebben deze structuren uitgebreid met allerlei nieuwe problemen en klassen. Met de opkomst van multicoreprocessors en quantum computing zijn met name Nick's Class en BQP in de belangstelling komen te staan.

Nick's Class bevat alle problemen die met een parallelle Turing-machine in polylogaritmische tijd zijn op te lossen, dat wil zeggen: sneller dan polynomiaal. Zo'n parallel systeem bestaat uit een beperkt aantal rekeneenheden rond een gedeeld geheugen. Omdat een DTM een parallel random access machine kan simuleren, vallen de problemen in NC ook in P. Tegelijkertijd is het vermoeden dat er ook problemen zijn die geen voordeel hebben bij meerdere rekeneenheden, en dus inherent sequentieel zijn. Die klasse van problemen die wel in P vallen maar niet in NC, heet P-Compleet.

Dit theoretische concept zien we terug in de softwarewereld, waar de Wet van Amdahl een relatie legt tussen de parallelliseerbaarheid van een algoritme en de maximale versnelling die kan worden verkregen op een parallelle computer.

Quantum computers

BQP, kort voor Bounded Error Quantum Polynomial, bevat de problemen die, in elk geval hoogstwaarschijnlijk, in polynomiale tijd op een quantum-Turing-machine zijn op te lossen. Daarbij moet het aantal quantum bits weer polynomiaal beperkt zijn ten opzichte van de input string. De BQP-klasse omvat wel P, maar niet NP-Compleet. Dat betekent dat een quantumcomputer niet fundamenteel krachtiger is dan een traditionele computer, en alleen sneller is voor bepaalde NP-Intermediate problemen. Maar onbeslisbare problemen blijven onbeslisbaar, en NP-Complete problemen blijven niet-polynomiaal.

BQP Complexity Class Diagram (Wikipedia)

Helaas voor de veiligheidsleveranciers valt het algoritme van Shor binnen de klasse BQP. Dat wil zeggen dat er een quantumalgoritme bestaat waarmee de priemfactoren van getallen kunnen worden gevonden. Het in priemfactoren ontbinden van getallen is een NP-probleem, en de moeilijkheid daarvan is de basis van de public-keycryptografie die we dagelijks op het internet gebruiken. Dat betekent dat we op termijn nieuwe algoritmen moeten inzetten die informatie-theoretisch veilig zijn.

Inhoudsopgave

Multipage-opmaak

IT-banen

Reacties (51)

TeGek 23 juni 2012 10:10

Leuk artikel en wel duidelijk, alleen was het misschien ook leuk in de intro de mindere kanten te vertellen over wat turing is aangedaan;

In 52 heeft de britste staat hem aangeklaagd voor homoseksualiteit en gaf hem een keuze; chemische castratie of een levenslange gevangenisstraf, hiervoor is geen excuus gebracht tot 2010 - en zelfs in dit excuus heeft de britste staat niet officieel gemeld dat het excuus over de chemische castratie ging.

Ook wouden de Britten de al Turings uitvindingen(het kraken van de enigma code, etc) niet onder turing's eigen naam laten vallen maar onder de naam van de staat - Dit omdat hun vonden dat een homoseksueel geen wetenschaplijk genie kon zijn.

voor de rest, prima en mooi artikel. Wonderbaarlijk man die Turing.

MicGlou @TeGek • 24 juni 2012 13:41

U vraagt...

http://www.bbc.co.uk/news/science-environment-18561092

Dit weekend is daar blijkbaar uitgebreid over gesproken... er wordt nu zelfs openlijk aan zijn zelfmoord getwijfeld... alhoewel het een 'ongeluk' wordt genoemd.

Ook al Bezet @TeGek • 23 juni 2012 12:18

Turing is inderdaad schandalig behandeld, maar over zijn zelfmoord schijnen toch twijfels te bestaan.

blobber @TeGek • 23 juni 2012 12:39

nvm, dubbel

[Reactie gewijzigd door blobber op 22 juli 2024 14:01]

justinkb 23 juni 2012 10:11

P en NP zijn niet de enige klassen (bijv. EXPTIME wordt vergeten, waarin problemen zitten die zeker moeilijker zijn dan de problemen in P en NP), dus in het P = NP? deel moet e.e.a. herschreven worden.

Bovendien is het jammer dat de schrijver al aanneemt dat P != NP, bijvoorbeeld in deze zin:

"Deze Niet-deterministisch Polynomiale problemen zijn alleen op te lossen met algoritmen waarvan de rekentijd sneller dan polynomiaal toeneemt als de invoerstring langer wordt."

Dat is natuurlijk alleen waar onder aanname dat P != NP, maar die aanname staat nergens vermeld.

Virtlink @justinkb • 23 juni 2012 11:54

Niemand beweert dat NP-compleet de klasse met moeilijkste problemen is. Ik zie niet wat er mis is met het stukje P =? NP, want het is een heel terechte vraag die meer te maken heeft met Turing-machines dan de klassen EXPTIME of NP-hard.

Die aanname P != NP is heel logisch en staat wél in het artikel:

De vraag of uiteindelijk voor alle problemen in de klasse NP een polynomiaal algoritme kan worden gevonden, waarmee die problemen dus in de klasse P terecht komen, wordt door de theoretici P =? NP genoemd. Het vermoeden is echter dat er problemen zijn waarvoor helemaal geen P-algoritme kan bestaan, maar dat bewijzen is vers twee. Dit is niet voor niets een van de zeven Millennium-vraagstukken, waar een geldprijs van een miljoen dollar aan is verbonden.

Bovendien lijken er problemen te zijn die wel in NP zitten maar niet in P of NP-Compleet.

justinkb @Virtlink • 23 juni 2012 15:07

in dat stukje van het artikel staat letterlijk dat - aangenomen dat P != NP - niet-P problemen dientengevolge in NP zitten, totale onzin dus.

overigens, het stukje wat jij quote is een mooi voorbeeld van nog een foute formulering door onzorgvuldigheid:

"Het vermoeden is echter dat er problemen zijn waarvoor helemaal geen P-algoritme kan bestaan." Wat bedoeld wordt: "Het vermoeden is echter dat er problemen in klasse NP zijn waarvoor helemaal geen P-algoritme kan bestaan"

Als je wetenschappelijk bezig wil wezen, moet je wel precies te werk gaan (mathematical rigor).

@Garma, de formulering zoals ie er nu staat kun je niet uitleggen als kloppend, zonder P != NP aan te nemen. Je draait de zaak juist om, je zegt dat omdat er nog niet zo'n algoritme gevonden is, dat P dus niet gelijk is aan NP. De quote "Deze Niet-deterministisch Polynomiale problemen zijn alleen op te lossen met algoritmen waarvan de rekentijd sneller dan polynomiaal toeneemt als de invoerstring langer wordt." is _juist_ de essentie van P = NP? vraag.

[Reactie gewijzigd door justinkb op 22 juli 2024 14:01]

z.jeroen @justinkb • 23 juni 2012 23:16

Je kunt de formulering wel uitleggen als kloppend met een beetje goede wil:

"Deze Niet-deterministisch Polynomiale problemen zijn (op dit moment) alleen op te lossen met algoritmen waarvan de rekentijd sneller dan polynomiaal toeneemt als de invoerstring langer wordt."

Garma @justinkb • 23 juni 2012 13:09

"Deze Niet-deterministisch Polynomiale problemen zijn alleen op te lossen met algoritmen waarvan de rekentijd sneller dan polynomiaal toeneemt als de invoerstring langer wordt."

Dat is natuurlijk alleen waar onder aanname dat P != NP, maar die aanname staat nergens vermeld.

volgens mij klopt het artikel strikt genomen wel, want zolang er geen bewijs is voor P = NP dan is er dus geen algoritme dat NP problemen sneller oplost. Het zou kunnen dat er wel een algoritme is, maar dat is op dit moment in elk geval niet bekend. P =? NP gaat over de vraag of dat algoritme uberhaupt bestaat.

sirdupre 23 juni 2012 10:23

Leuk om een verhaal over complexiteit te zien op Tweakers! Het is inderdaad een erg nuttige theorie om ingewikkelde praktische problemen te bestuderen. De opgedane kennis kun je vervolgens gebruiken in het ontwerp van je oplossingsmethoden. Veel roosterings- en planningsproblemen uit de praktijk zijn NP-hard. Vaak hebben dit soort problemen wel weer deelproblemen die wel efficient op te lossen zijn. Soms kun je de oplossing van een makkelijk deelprobleem gebruiken om iets nuttigs te zeggen over de best mogelijke oplossing voor het moeilijke probleem.

Wat mij betreft is er op dat gebied ook een keerzijde aan de theorie van NP-volledigheid: zodra bekend is dat een probleem "lastig" is geven mensen het al snel op om goede oplossingsmethoden te verzinnen. Toch geldt vaak voor veel praktische problemen dat je een heel eind kunt komen. Zo zijn er voor het genoemde handelsreizigersprobleem programma's die instanties met een paar honderd steden in een seconde kunnen oplossen (en staat het wereldrecord op 85900 steden voor het ontwerp van een chip). Over deze ontwikkeling is vorig jaar nog een voor leken geschikt boek, "In pursuit of the traveling salesman" uitgekomen, wat zeker een aanrader is.

Voor tweakers die de complexiteitstheorie an sich interessant vinden is er vorig jaar ook nog een enorm boek uitgekomen dat deze onderwerpen op een wat speelse, maar veel diepgaandere manier uitlegt: "The nature of computation".

Auteur

offerman 23 juni 2012 12:42

Nog een lichtvoetiger aanvulling: vorige week is de film "Travelling Salesman" in premiere gegaan. Daarin wordt uitgewerkt wat er zou gebeuren als P=NP.

Site film:
http://www.travellingsalesmanmovie.com/

roy-t 23 juni 2012 12:50

Leuk om iets over complexiteitstheorie te zien. De vraag P=NP is trouwens minder belangrijk dan we misschien denken, R.J. Lipton heeft daar een leuk stuk over geschreven: http://rjlipton.wordpress...pnp-an-ill-posed-problem/

Daar staat ook een goede quote in van Alan Perlis:

For every polynomial algorithm you have, I have an exponential algorithm that I would rather run.

Anoniem: 64607 23 juni 2012 10:16

Leuk fimpje, behalve dat het compleet niet laat zien hoe 2+2 uitgerekend wordt door de machine (misschien was dat ook een beetje teveel verwacht).

JeroenB @Anoniem: 64607 • 23 juni 2012 11:48

Probleem is dat'ie daar vijf minuten over doet

Maar voor wat extra uitleg over de werking, zie http://www.legoturingmachine.org/, daar staan ook links naar de implementatie van het optelprogramma e.d.

Makkelijk @JeroenB • 23 juni 2012 22:00

Als je echt pech hebt komt er 3 uit

Ettepet 23 juni 2012 10:09

"Het in priemfactoren ontbinden van getallen is een NP-probleem"

Het ontbinden in factoren van een getal is puur een P-probleem, met zelfs een bijzonder eenvoudig algoritme. Pas als je niet het getal zelf maar de lengte van het getal als invoerparameter neemt (dus de logaritme van het getal i.p.v. het getal zelf) dan introduceer je daarmee automatisch (logaritme <-> exponentieel) een exponentieel verloop, en dus NP.

FSVZ @Ettepet • 23 juni 2012 11:47

Het ontbinden van een getal in zijn priemgetallen is niet(deterministisch) polynomiaal. Het testen dat de oplossingen correct is polynomiaal. Dus het ontbinden van een getal in zijn priemfactoren is wel degelijk NP. Ik snap dan ook niet wat dat dan te maken heeft met de "de lengte van het getal als invoerparameter"...

Mocht je gelijk hebben, dan heb je een bewijs gegeven dat P=NP. En dat lijkt me een beetje sterk en zullen een aantal jongens in o.a. de cripto-wereld erg nerveus worden.

Edit: toevoeging tweede alinea.

[Reactie gewijzigd door FSVZ op 22 juli 2024 14:01]

z.jeroen @FSVZ • 23 juni 2012 22:46

Je bedoelt: er is geen polynomiale-tijd algoritme bekend voor priemontbinding. Of het probleem van priemontbinding wel of niet in P zit, weten we niet. Je hebt verder helemaal gelijk.

Wat Ettepet zegt is: als je de tijdscomplexiteit uitdrukt in termen van de invoer zelf, in plaats van de bitlengte van de invoer, dan is de complexiteit lager en zit priemontbinding in P. Dat is onzin, omdat dat niet de definitie van P is.

[Reactie gewijzigd door z.jeroen op 22 juli 2024 14:01]

Apocalypsy 23 juni 2012 08:48

Heb hier net een examen over gehad. Best wel interessant en vrij goed uitgelegd zodat een iets of wat meer leek dat ook wel kan verstaan.

kwinvdv @Apocalypsy • 23 juni 2012 17:10

Maar ik snap nog niet helemaal om wat voor een soort problemen hier hier gaat. Gaan deze theorieën over wiskundige problemen, zoals differentiaal vergelijkingen. Want ik kan mij niet voorstellen dat je een ander soort probleem op zo'n Turning tape kan formuleren.

[Reactie gewijzigd door kwinvdv op 22 juli 2024 14:01]

z.jeroen @kwinvdv • 23 juni 2012 22:41

Formeel gaat het om problemen met een ja/nee-antwoord, zogenaamde decision problems. Bijvoorbeeld: is x een priemgetal? Maar het kan ook zijn: is f een oplossing van de differentiaalvergelijking x? of: heeft de vergelijking x een oplossing?

[Reactie gewijzigd door z.jeroen op 22 juli 2024 14:01]

Pouja @kwinvdv • 23 juni 2012 19:32

"Maar ik nog niet helemaal om wat voor een soort problemen hier hier gaat."
Allerlei soorten problemen, van het vinden een kortste pad in een graaf tot het decoderen van berichten.

"Gaan deze theorieën over wiskundige problemen, zoals differentiaal vergelijkingen."
Nee, de turing theorien, om het maar zo op te noemen, worden vaak gebruikt om problemen te classificeren.

"Want ik kan mij niet voorstellen dat je een anders soort probleem op zo'n Turning tape kan formuleren."
Ja dat is mogelijk, want elk probleem kan je zo formuleren dat er een Turning Machine er voor kan worden gemaakt.

beyonix @Pouja • 25 juni 2012 10:51

Een kleine toevoeging: Voor de zogenaamde onbeslisbare problemen geld dus dat er juist geen TM voor gemaakt kan worden. Het halting probleem beschreven in het artikel is hier een voorbeeld van.

Jogai 23 juni 2012 07:47

Duidelijk verhaal. Ik had het idee dat een turing-machine de turing-test kon doorstaan, maar het gaat dus over 2 compleet verschillende dingen. Alleen de naam heeft nogal een grote overeenkomst.

Gropah @Jogai • 23 juni 2012 18:51

De turingtest gaat over hoe goed een computer een mens na kan doen, terwijl de turing machine gaat over wat de computer kan.

Geeft maar weer aan met hoeveel gebieden Turing zich bezig hield. Naast KI en Informatica deed hij namelijk ook nog aan oa encryptie en biologie.

huub8 @Gropah • 24 juni 2012 01:27

De turingtest gaat over de intelligentie van een systeem, niet perse het nadoen van een mens.

Anoniem: 249623 @huub8 • 24 juni 2012 12:48

Ik vraag me af of jullie het wel gelezen hebben.

Een computer gaat door de Turing test succesvol wanneer het een mens heeft weten te overtuigen dat het zelf ook een mens is. Intelligentie heeft hier niks mee te maken, dit is Weak AI. Een computer dat daadwerkelijk intelligent is noem je een Strong AI.

Alan heeft met zoveel gebieden bezig gehouden omdat hij initieel bezig hield met KI, maar om KI te maken had hij een machine nodig die dat kon doen. Hiervoor had een machine nodig die dat kon doen, hij is toen een (theoritische) computer gaan ontwikkelen die dit kon. Dit is uiteindelijk de Turing machine geworden.

http://en.wikipedia.org/wiki/Turing_test
http://en.wikipedia.org/wiki/Strong_AI_vs._weak_AI
http://en.wikipedia.org/w...achinery_and_Intelligence

[Reactie gewijzigd door Anoniem: 249623 op 22 juli 2024 14:01]