Optaget bæver

I beregnelighed, en travl bæver er en Turing-maskine, der opnår det maksimale antal trin, der udføres, eller maksimalt antal nonblank symboler endelig på båndet, blandt alle Turing-maskiner i en bestemt klasse. Turing-maskiner i denne klasse skal opfylde visse design specifikationer og er forpligtet til sidst standse efter at være i gang med et tomt bånd.

En travl bæver funktion kvantificerer disse øvre grænser for en given foranstaltning, og er en noncomputable funktion. Faktisk kan en optaget beaver funktionen vist sig at vokse hurtigere asymptotisk end nogen beregnelige funktion. Konceptet blev først introduceret af Tibor Rado som "optaget bæver spil" i hans 1962 papir, "på ikke-beregnelige funktioner".

Den travle bæver spil

N-state travlt bæver spil, der blev indført i Tibor Rado 1962 papir, involverer en klasse af Turing-maskiner, hvert medlem, der er nødvendige for at opfylde følgende specifikationer:

  • Maskinen har n "operationelle" stater plus en Halt tilstand, hvor n er et positivt heltal, og en af ​​de n stater adskiller som udgangsmateriale stat.
  • Maskinen bruger en enkelt to-vejs uendelig tape.
  • Båndet alfabetet er {0, 1}, hvor 0 tjener som den tomme symbol.
  • Maskinens overgang funktion tager to indgange:

"Kører" maskinen består i at starte i start tilstand, med den nuværende tape celle er nogen celle i et tomt bånd, og derefter iteration overgangen funktionen indtil Halt tilstand er indtastet. Hvis, og kun hvis, maskinen sidst standser, så antallet af 1s endelig tilbage på båndet kaldes maskinens score.

N-state travlt bæver spil er en konkurrence for at finde sådan en n-state Turing-maskine der har den størst mulige score det største antal 1s på bånd efter at standse. En maskine, der opnår den største mulige score blandt alle n-state Turing-maskiner kaldes en n-state travlt bæver, og en maskine, hvis score er blot det højeste hidtil opnået kaldes en mester n-state maskine.

Rado kræves, at hver maskine indtastet i konkurrencen være ledsaget af en angivelse af den nøjagtige antal skridt, det tager at nå Halt tilstand, således at scoren for hver post, der skal kontrolleres ved at køre maskinen til det angivne antal trin.

Den travle bæver funktion Σ

Den travle bæver-funktion, Σ: N → N er defineret således, at Σ er den maksimalt opnåelige score blandt alle standse 2-symbolet n-state Turing-maskiner af den ovenfor beskrevne type, når den startes på et tomt bånd.

Det er klart, at Σ er en veldefineret funktion: for alle n, er der højst endelig mange n-state Turing-maskiner som ovenfor, op til isomorfi, dermed højst finitely mange mulige kørende gange.

Denne uendelige sekvens Σ er den travle bæver-funktionen, og enhver n-tilstand 2-symbolet Turing-maskine M, for hvilken a = Σ kaldes en travl bæver. Bemærk, at for hvert n, der findes mindst to n-state travle bævere.

Ikke-beregnelighed af Σ

Rado 1962 papir bevist, at hvis f: N → N er enhver beregnelig funktion, så Σ & gt; f for alle tilstrækkeligt store n, og dermed at Σ er ikke en beregnelige funktion.

Desuden indebærer dette, at det er uafgørbart ved en generel algoritme, om en vilkårlig Turing-maskine er en travl bæver. (En sådan algoritme kan ikke eksistere, fordi dens eksistens ville tillade Σ skal beregnes, hvilket er en gennemprøvet umuligt Især kunne en sådan algoritme anvendes til at konstruere en anden algoritme, der vil beregne Σ som følger:. For en given n, idet hver af de endeligt mange n-state 2-symbol Turing-maskiner vil blive testet, indtil en n-state travlt bæver er fundet denne travle bæver maskine ville så simuleres at bestemme dens score, hvilket er per definition Σ).

Selvom Σ er en uberegnelige funktion, der er nogle små n, hvor det er muligt at opnå sine værdier, og bevise, at de er korrekte. Det er ikke svært at vise, at Σ = 0, Σ = 1, Σ = 4, og med gradvist mere besvær kan det vises, at Σ = 6 og Σ = 13. Σ er endnu ikke bestemt for enhver forekomst af n & gt; 4, selv om der er etableret nedre grænser.

Σ, kompleksitet og manglende dokumentation

En variant af Kolmogorov kompleksitet er defineret som følger: Kompleksiteten af ​​et tal n er det mindste antal stater, der er nødvendige for en BB-klasse Turing-maskine, der stopper med en enkelt blok af n på hinanden følgende 1s på en oprindelig tomt bånd. Den tilsvarende variant af Chaitin s ufuldstændige sætning hedder det, i forbindelse med en given aksiomatiske system til de naturlige tal, findes der en række k, således at ingen specifik nummer kan bevises at have kompleksiteten større end k, og dermed, at ingen specifik øvre grænse det kan dokumenteres, Σ (sidstnævnte er fordi "kompleksiteten af ​​n er større end k" ville bevises, hvis "n & gt; Σ" blev bevist). Som nævnt i den citerede reference for enhver aksiomatisk system for "almindelige matematik" den mindste værdi k for hvilke dette er sandt, er langt mindre end 10 ↑↑ 10; dermed i forbindelse med almindelige matematik, hverken værdien eller nogen øvre grænse for Σ kan bevises. (Gödel første ufuldstændige sætning er illustreret ved dette resultat: i et aksiomatisk system almindelige matematik, der er en sand-men-ubevislig punktum i formen "Σ = n", og der er uendeligt mange virkelighedstro men-ubevislig punktum danne "Σ & lt; n").

Max skifter funktion

Ud over funktionen Σ, Rado introducerede en anden ekstrem funktion for BB-klassen af ​​Turing-maskiner, den maksimale skift funktion, S, defineret som følger:

  • antallet af skift M gør før standse, for enhver M i En,
  • det største antal skift fra en hvilken som helst standse n-tilstand 2-symbolet Turing-maskine.

Fordi disse Turing-maskiner er forpligtet til at have et skift i hver eneste overgang eller "trin", Max-skift funktion er samtidig en max-trin-funktion.

Rado viste, at S er noncomputable af samme grund, at Σ er noncomputable den vokser hurtigere end nogen beregnelige funktion. Han beviste dette blot ved at bemærke, at der for hvert n, S ≥ Σ, fordi et skift er forpligtet til at skrive en 1 på båndet; følgelig S vokser mindst lige så hurtigt som Σ, som allerede var blevet bevist at vokse hurtigere end nogen beregnelige funktion.

Den følgende forbindelse mellem Σ og S blev brugt af Lin & amp; Rado at bevise, at Σ = 6: For en given n, hvis S er kendt derefter alle n-state Turing-maskiner kan køres op til S trin, på hvilket tidspunkt en hvilken som helst maskine, der endnu ikke er stoppet, vil aldrig standse. På det tidspunkt, ved at iagttage hvilke maskiner har standset med flest 1s på båndet, opnår man fra deres bånd værdien af ​​Σ. Den anvendes af Lin & amp tilgang; Rado i tilfælde af n = 3 var at formode, at S = 21, derefter at simulere alle væsensforskellige 3-state maskiner i op til 21 trin. Ved at analysere adfærd maskiner, der ikke havde standset inden for 21 trin, lykkedes det at vise, at ingen af ​​disse maskiner nogensinde ville standse, og dermed bevise formodninger, at S = 21, og bestemme, at Σ = 6 ved proceduren netop beskrevet.

Uligheder vedrørende Σ og S omfatter følgende, som er gældende for alle n ≥ 1:

og en asymptotisk forbedret bundet: der findes en konstant c, således at der for alle n ≥ 2,

Kendte værdier

Funktionen værdier for Σ og S er eneste kendte præcis for n & lt; 5. Den nuværende 5-state travlt bæver mester producerer 4.098 1s, hjælp 47,176,870 trin, men der er stadig omkring 40 maskiner med ikke-regelmæssig adfærd, der menes at aldrig standse, men som endnu ikke er blevet bevist til at køre uendeligt. I øjeblikket rekorden 6-state travlt bæver producerer over 10 1s, brug af over 10 trin. Som bemærket ovenfor, disse travle bævere er 2-symbol Turing-maskiner.

Milton Green, i hans 1964 papir "en nedre grænse på Rado s Sigma Funktion til Binary Turing-maskiner", konstrueret et sæt Turing-maskiner der viser, at

hvor er Knuth up-pil notation og A er Ackermann funktion.

Dermed

Og

hvor antallet G1 er den enorme startværdi i sekvensen, der definerer Graham nummer.

I modsætning hertil er den nuværende grænse for Σ er 10, som er større end den nedre grænse 3 = 27. Faktisk er det er meget større end den nedre grænse:, som er Greens bundet til.

Generaliseringer

For enhver model for beregning findes der simple analoger af den travle bæver. For eksempel generalisering til Turing-maskiner med n stater og m symboler definerer følgende generelle travle bæver funktioner:

  • Σ: det største antal ikke-nuller printes med en n-state, m-symbolet maskine i gang med en oprindelig tomt bånd før standse, og
  • S: det største antal skridt, som en n-state, m-symbolet maskine i gang med en oprindelig tomt bånd før standse.

For eksempel den længste kører 3-tilstand 3-symbol maskine fundet indtil videre kører 119,112,334,170,342,540 trin før standse. Den længste kører 6-state, 2-symbol maskine, der har den yderligere egenskab vende båndet værdi ved hvert trin producerer 6,147 1s efter 47,339,970 trin. Så SRTM ≥ 47339970 og ΣRTM ≥ 6147.

Det er muligt yderligere at generalisere optaget Beaver funktionen ved at lade mere end en dimension.

Ligeledes kunne vi definere en analog til Σ funktion for registerbaserede maskiner som det største tal, der kan være til stede i ethvert register på standse, for et givet antal instruktioner.

Applikationer

Ud over at udgøre en temmelig udfordrende matematisk spil de travle bæver funktioner, tilbyder en helt ny tilgang til at løse ren matematik problemer. Mange åbne problemer i matematik kunne i teorien, men ikke i praksis, løses på en systematisk måde givet værdien af ​​S for et tilstrækkeligt stort n.

Overveje nogen formodninger, der kunne modbevist via en modeksempel blandt en tællelig antal sager. Skriv et computerprogram, der sekventielt tester denne formodning ved voksende værdier. I tilfældet med Goldbachs formodning, vil vi overveje hver lige antal ≥ 4 sekventielt og teste, om det ikke er summen af ​​to primtal. Antag dette program er simuleret på en n-state Turing-maskine. Hvis den finder et modeksempel, det stopper og meddeler os. Men hvis formodningen er sand, så er vores program vil aldrig standse.

Nu er dette program simuleres ved en n-state Turing-maskine, så hvis vi ved S vi kan beslutte, om det nogensinde vil standse ved blot at køre den maskine, mange trin. Og hvis, efter S-trin, maskinen ikke standse, ved vi, at det aldrig vil, og dermed at der ikke er modeksempler til den givne formodninger. Dette ville bevise formodninger til at være sandt.

Således kunne bruges særlige værdier for S til systematisk at løse mange åbne problemer i matematik. Men de aktuelle resultater på den travle bæver problemet tyder på, at dette ikke vil være praktisk af to grunde:

  • Det er ekstremt svært at bevise værdier for den travle bæver-funktionen. Det er kun blevet bevist til ekstremt små maskiner med færre end 5 stater, mens man formentlig ville brug for mindst 20-50 stater til at yde et nyttigt maskine. Desuden blev alle kendte nøjagtige værdi af S bevist ved at opremse alle n-state Turing-maskine og bevise, hvorvidt hver stopper. Man ville være nødt til at beregne S af nogle mindre direkte metode til det faktisk at være nyttig.
  • Men selv om man fandt en bedre måde at beregne S, værdierne af den travle bæver funktionen blive meget store, meget hurtigt. S & gt; 10 allerede kræver særlig mønsterbaseret acceleration at kunne simulere til afslutning. Ligeledes ved vi, at er en gigantisk nummer. Selv om vi vidste, siger, S, det er helt urimeligt at køre enhver maskine, antal trin. Der er ikke nok beregningsmæssige kapacitet i det kendte univers for at have udført selv S operationer direkte.

Bevis for uncomputability af S og Σ

Antag, at S er en beregnelig funktion og lad EvalS betegne en TM, evaluering S. Givet et bånd med n 1s det vil producere S 1s på båndet og derefter standse. Lad Clean betegne en Turing-maskine rengøring sekvensen af ​​1s oprindeligt skrevet på båndet. Lad Dobbelt betegne en Turing-maskine evaluere funktion n + n. Givet et bånd med n 1s det vil producere 2n 1s på båndet og derefter standse. Lad os skabe sammensætningen Dobbelt | EvalS | Rens og lad n0 være antallet af tilstande af denne maskine. Lad Create_n0 betegne en Turing-maskine skaber n0 1s på en oprindelig tomt bånd. Denne maskine kan konstrueres på en triviel måde at have N0 stater. Lad N betegne summen n0 + n0.

Lad onder betegne sammensætningen Create_n0 | Dobbelt | EvalS | Ren. Bemærk at denne maskine har N stater. Startende med en oprindelig tomt bånd det første skaber en sekvens af n0 1s og så fordobler den, der producerer en sekvens af N 1s. Så onder vil producere S 1s på bånd, og til sidst vil det rydde alle 1s og derefter standse. Men fase af rengøring vil fortsætte mindst S trin, så tidspunktet for bearbejdning af Bads er strengt større end S, hvilket er i modstrid med definitionen af ​​funktionen S.

Den uncomputability af Σ kan bevises på samme måde. I ovenstående bevis, må man bytte maskinen EvalS med EvalΣ og Rengør med Interval - en simpel TM, der søger efter en første 0 på båndet og erstatte den med en.

Den uncomputability S kan også etableres med henvisning til den tomme bånd standse problem. Den tomt bånd standse problem er problemet med at beslutte for enhver Turing-maskine, hvorvidt det vil standse ved start på en tom bånd. Den tomt bånd standse problem svarer til standard standse problem, og så er det også uberegnelige. Hvis S var beregnelige, så kunne vi løse det tomt bånd standse problemet blot ved at køre en given Turing-maskine med n stater for S trin; hvis det stadig ikke har standset, er det aldrig vil. Så da den tomme bånd standse problem er ikke beregnelige, følger det, at S ligeledes skal være uberegnelige.

Eksempler

Disse er tabeller af regler for Turing-maskiner, der genererer Σ og S, Σ og S, Σ (men ikke S), Σ og S, og den bedst kendte nedre grænse for Σ og S, og Σ og S.

I tabellerne repræsenterer kolonner den aktuelle tilstand og rækker repræsenterer den aktuelle symbol læses fra båndet. Hver tabel post er en streng af tre tegn, angiver symbolet for at skrive på båndet, til retningen flytte, og den nye tilstand. Standsningstilstanden er vist som H.

Hver maskine begynder i tilstand A med en uendelig tape, der indeholder alle 0'erne. Således oprindelige symbol læses fra båndet er et 0.

Resultat Tast:

Resultat: 0 0 1 0 0

Resultat: 0 0 1 1 1 1 0 0

Resultat: 0 0 1 1 1 1 1 1 0 0.

I modsætning til de tidligere maskiner, denne ene er en travl bæver kun for Σ, men ikke for S. (S = 21)

Resultat: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0

Resultat: 4098 "1" s med 8191 "0" s afbrudt i 47,176,870 trin.

Resultat: ≈3.515 × 10 "1" 'ere i ≈7.412 × 10 trin.

Nøjagtige værdier og nedre grænser for nogle S og Σ

Følgende tabel viser de nøjagtige værdier og nogle kendte nedre grænser for S og Σ for de generaliserede travle bæver problemer. Kendte eksakte værdier er vist som almindelige heltal og kendte nedre grænser indledes med en større end eller lig med symbolet. Bemærk: angivelserne som "???" er afgrænset fra neden af ​​maksimum af alle indgange til venstre og over. Disse maskiner har enten ikke blevet undersøgt eller var blevet overgået af en maskine forud for disse.

Turing-maskiner, der opnår disse værdier er tilgængelige på begge Heiner Marxen s og Pascal Michel websider. Hver af disse hjemmesider indeholder også en analyse af de Turing-maskiner og henvisninger til de beviser for de nøjagtige værdier.

Værdier af S:

Værdier af Σ:

  0   0
Forrige artikel Dennis Hart Mahan
Næste artikel CorbacI

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha