Berekenbaarheidsteorie

in Wikipedia, die vrye ensiklopedie
Jump to navigation Jump to search

Berekenbaarheidsteorie, ook bekend as rekursieteorie, 'n tak van wiskundige logika, van rekenaarwetenskap, en van die teorie van berekentasie wat in die 1930s ontstaan het met die studie van berekenbare funksies en Turing graads. Die veld het sedertdien uitgebrei om die studie van algemene berekenbaarheid en bepaalvermoë. Op hierdie gebied, oorvleuel die berekenbaarheidsteorie met die bewysteorie en doeltreffende beskrywende stelteorie.

Basiese vrae aangespreek deur die berekenbaarheidsteorie sluit in:

  • Wat beteken dit vir 'n funksie op die natuurlike getalle om berekenbaar te wees?
  • Hoe kan nie-berekenbare funksies in 'n hiërargie geklassifiseer word op grond van hul vlak van nie-berekenbaarheid?

Alhoewel daar aansienlike oorvleuel in terme van kennis en metodes, wiskundige resion teoretiste bestudeer die teorie van relatiewe berekenbaarheid, redusibility opvattings, en graad strukture; diegene in die rekenaarwetenskap-veld fokus op die teorie van subrekursiewe hiërargieë, formele metodes, en formele tale.[1][2]

Turing berekenbaarheid[wysig | wysig bron]

Die belangrikste vorm van berekenbaarheid bestudeer in resion-teorie is bekendgestel deur Turing (1936). 'N stel natuurlike getalle word gesê dat dit 'n berekenbare stel (ook genoem 'n decibare, rekursiewe, of Turing berekenbare stel) As daar is 'n Turing masjien dat, gegewe 'n getal n, buurtwagte met uitset 1 in n die in die stel en buurtwagte met uitset 0 in n is nie in die stel. 'N funksie f van die natuurlike getalle tot hulself is 'n rekursiewe of (Turing) berekenbare funksie in Daar is 'n Turing masjien wat, op insette n, buurtwagte en opbrengste uitset f(n). Die gebruik van die Turing masjiene hier is nie nodig nie; Daar is baie ander modelle van berekeningtasie wat dieselfde rekenaarkrag het as die versiering van Turing masjiene; byvoorbeeld die μ-rekursiewe funksies verkry van primitiewe resion en die μ-operateur.

Die terminologie vir rekursiewe funksies en stelle is nie heeltemal gestandaardiseerde. Die definisie in terme van μ-rekursiewe funksies sowel as 'n ander definisie van rekursiv funksies deur Gödel gelei tot die tradisionele naam rekursiewe vir stelle en funksies berekenbaar deur 'n bekende masjien. THy woord decibare stamme van die Duitse woord Entscheidungsproblem wat gebruik was in die oorspronklike vraestelle Turing en ander. In kontemporêre gebruik, die term  "berekenbare funksie" het verskeie definisies: volgens Cutland (1980) is dit 'n gedeeltelike rekursiewe funksie (wat vir sekere insette nie gedefinieer kan word nie), terwyl dit volgens Soare (1987) dit 'n totale rekursiewe, algemene rekursiewe funksie is. Hierdie artikel volg die tweede van hierdie konvensies. Soare (1996) gee bykomende kommentaar oor die terminologie.

Nie elke stel van natuurlike getalle is berekenbaar. Die staking probleem, wat is die versameling van (beskrywings van) in te stel masjiene wat stop op insette 0, is 'n bekende voorbeeld van 'n nie-berekenbare stel. Die bestaan van baie nie-berekenbare stelle volg van die feite dat daar net 'n telbaar baie Turing masjiene, en dus net so baie berekenbare stelle, maar volgens die Kantor se stelling, is daar onslanter baie stelle natuurlike getalle.

Alhoewel die halmende probleem is nie berekenbaar, is dit moontlik om programuitvoering te simuleer en 'n oneindige lys van die programme te produseer wat wel stop. Die staking probleem is dus 'n voorbeeld van 'n rekursief enumerseerbare stel, wat 'n stel is wat deur genommerde 'n Turing masjien (ander terme vir rekursief enumerseerbare insluit berekenbare enumerseerbare en semidecibare). In die gelykgestelde, 'n stel is rekursief enumerseerbare indien en net as dit is die omvang van 'n paar berekenbare funksie. Die rekursief enumerseerbare stelle, Alhoewel dit nie in die algemeen is nie, bestudeer in detail in rekursieteorie.

Verwysings[wysig | wysig bron]

  1. Soare, Robert Irving (22 December 2011). "Computability Theory and Applications: The Art of Classical Computability" (PDF). Department of Mathematics. University of Chicago. Besoek op 23 August 2017.
  2. Feferman et al. editors 1990 Kurt Gödel Volume II Publications 1938-1974, Oxford University Press, New York, ISBN 978-0-19-514721-6.

Eksterne skakels[wysig | wysig bron]