Hvis A ≤m B og B kan bestemmes, hvad kan vi så konkludere om afgøreligheden af A?
Inden for beregningsmæssig kompleksitetsteori spiller begrebet afgørelighed en vigtig rolle i forståelsen af grænserne for beregning. Afgørelighed refererer til evnen til at bestemme, om et givet problem eller sprog kan løses ved hjælp af en algoritme. I denne sammenhæng repræsenterer et sprog et sæt strenge over et givet alfabet.
Når vi overvejer forholdet mellem to sprog, A og B, analyserer vi ofte, om et sprog kan reduceres til et andet. En reduktion fra sprog A til sprog B er en transformation, der giver os mulighed for at løse forekomster af A ved hjælp af en algoritme for B. Denne reduktion er betegnet som A ≤m B, hvor "≤m" repræsenterer kortlægningsreduktionen.
Antag nu, at vi har en reduktion fra sprog A til sprog B, og vi ved, at sprog B kan bestemmes. Det betyder, at der eksisterer en algoritme, der kan bestemme medlemskab i B. Spørgsmålet opstår: hvad kan vi konkludere om afgøreligheden af sprog A?
For at besvare dette spørgsmål skal vi overveje reduktionens art. Hvis reduktionen er en polynomiel-tids-reduktion, også kendt som en polynomiel-tids-mange-en-reduktion, så kan vi konkludere, at hvis A ≤m B og B kan bestemmes, så er A også afgørbar.
En polynomiel-tidsreduktion er en kortlægningsreduktion, der kan beregnes i polynomiel tid. Det betyder, at vi for enhver inputforekomst af A kan transformere den til en forekomst af B i polynomisk tid. Ydermere vil resultatet af reduktionen have samme medlemskab som det oprindelige input. Med andre ord, hvis input tilhører A, så hører output til B, og omvendt.
Nøgleindsigten bag denne konklusion ligger i det faktum, at en polynomiel-tidsreduktion giver os mulighed for at løse forekomster af A ved først at transformere dem til forekomster af B og derefter anvende bestemmeren for B. Da B er afgørbar, kan vi bestemme, om den transformerede forekomst af B tilhører B eller ej. I forlængelse heraf kan vi også afgøre, om den oprindelige instans af A tilhører A eller ej.
For at illustrere dette koncept, lad os overveje et eksempel. Antag, at vi har to sprog, A og B, hvor A repræsenterer mængden af alle primtal og B repræsenterer mængden af alle lige tal. Vi ved, at B kan bestemmes, da vi nemt kan kontrollere, om et givet tal er lige eller ej. Lad os nu definere en reduktion fra A til B som følger: givet et inputtal n, transformerer vi det til 2n. Det er klart, at hvis n er primtal, så er 2n lige, og hvis n ikke er primtal, så er 2n ikke lige. Derfor kan vi løse forekomster af A ved at transformere dem til forekomster af B og anvende bestemmeren for B.
Hvis A ≤m B og B kan bestemmes, kan vi konkludere, at A også kan bestemmes, forudsat at reduktionen fra A til B er en polynomisk tidsreduktion. Dette resultat fremhæver styrken af reduktionsteknikker i forståelsen af sprogs afgørelighed og samspillet mellem forskellige beregningsmæssige problemer.
Andre seneste spørgsmål og svar vedr afgørbarhed:
- Kan et bånd begrænses til størrelsen af inputtet (hvilket svarer til, at turingmaskinens hoved er begrænset til at bevæge sig ud over TM-båndets input)?
- Hvad betyder det, at forskellige varianter af Turing-maskiner er ækvivalente med hensyn til computerkapacitet?
- Kan et genkendeligt sprog danne en delmængde af afgøreligt sprog?
- Er stopproblemet med en Turing-maskine afgøreligt?
- Hvis vi har to TM'er, der beskriver et sprog, der kan afgøres, er ækvivalensspørgsmålet stadig uafgørligt?
- Hvordan adskiller acceptproblemet for lineært afgrænsede automater sig fra det for Turing-maskiner?
- Giv et eksempel på et problem, der kan afgøres af en lineært afgrænset automat.
- Forklar begrebet afgørelighed i sammenhæng med lineært afgrænsede automater.
- Hvordan påvirker størrelsen af båndet i lineært afgrænsede automater antallet af distinkte konfigurationer?
- Hvad er den største forskel mellem lineært afgrænsede automater og Turing-maskiner?
Se flere spørgsmål og svar i Afgørelighed