Reducerbarhed er et grundlæggende begreb i beregningsmæssig kompleksitetsteori, der spiller en vigtig rolle i at bevise uafgørelighed. Det er en teknik, der bruges til at fastslå et problems uafgørelighed ved at reducere det til et kendt uafgørligt problem. I bund og grund giver reducerbarhed os mulighed for at vise, at hvis vi havde en algoritme til at løse det pågældende problem, kunne vi bruge den til at løse det kendte uafklarelige problem, hvilket er en selvmodsigelse.
For at forstå reducerbarhed, lad os først definere begrebet et beslutningsproblem. Et beslutningsproblem er et beregningsproblem, der kræver et ja/nej-svar. For eksempel er problemet med at bestemme, om et givet tal er primtal eller sammensat, et beslutningsproblem. Vi kan repræsentere beslutningsproblemer som formelle sprog, hvor strengene i sproget er de tilfælde, hvor svaret er "ja".
Lad os nu overveje to beslutningsproblemer, P og Q. Vi siger, at P kan reduceres til Q (betegnet som P ≤ Q), hvis der eksisterer en beregnelig funktion f, der transformerer forekomster af P til forekomster af Q på en sådan måde, at svaret til en instans er x af P "ja", hvis og kun hvis svaret på f(x) af Q er "ja". Med andre ord bevarer f svaret på problemet.
Nøgletanken bag reducerbarhed er, at hvis vi kan reducere problem P til problem Q, så er Q mindst lige så hårdt som P. Hvis vi havde en algoritme til at løse Q, kunne vi bruge den sammen med reduktionsfunktionen f til at løse P. Det betyder, at hvis Q er uafgøreligt, så skal P også være uafgørligt. Reducerbarheden giver os således mulighed for at "overføre" uafgøreligheden fra et problem til et andet.
For at bevise uafgørelighed ved hjælp af reduktionsbarhed starter vi typisk med et kendt uafgørligt problem, såsom Halting Problemet, som spørger, om et givet program stopper på et givet input. Vi viser derefter, at hvis vi havde en algoritme til at løse vores interesseproblem, kunne vi bruge den til at løse Stop-problemet, hvilket fører til en modsigelse. Dette fastslår uafgøreligheden af vores problem.
Lad os for eksempel overveje problemet med at bestemme, om et givet program P accepterer input. Vi kan reducere stopproblemet til dette problem ved at konstruere en reduktionsfunktion f, der tager som input et program Q og et input x, og udsender et program P, der opfører sig som følger: hvis Q stopper på x, så accepterer P enhver input; ellers går P ind i en uendelig sløjfe for ethvert input. Hvis vi havde en algoritme til at løse problemet med at bestemme, om P accepterer noget input, kunne vi bruge det til at løse Stop-problemet ved at anvende det på f(Q, x). Derfor er problemet med at afgøre, om et program accepterer input, uafgørligt.
Reducerbarhed er en kraftfuld teknik inden for beregningsmæssig kompleksitetsteori, der giver os mulighed for at bevise, at et problem ikke kan afgøres ved at reducere det til et kendt problem, der ikke kan afgøres. Ved at etablere en reduktion fra et problem P til et problem Q viser vi, at Q er mindst lige så hårdt som P, og hvis Q er uafgørligt, så skal P også være uafgørligt. Denne teknik sætter os i stand til at overføre uafgørlighed mellem problemer og giver et værdifuldt værktøj til at forstå grænserne for beregning.
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