Hvis vi har to TM'er, der beskriver et sprog, der kan afgøres, er ækvivalensspørgsmålet stadig uafgørligt?
Inden for beregningsmæssig kompleksitetsteori spiller begrebet afgørelighed en grundlæggende rolle. Et sprog siges at kunne bestemmes, hvis der findes en Turing-maskine (TM), der kan bestemme, for et givet input, om det tilhører sproget eller ej. Et sprogs afgørelighed er en vigtig egenskab, da den giver os mulighed for at ræsonnere om sproget og dets egenskaber algoritmisk.
Ækvivalensspørgsmålet for Turing-maskiner handler om at bestemme, om to givne TM'er genkender det samme sprog. Formelt, givet to TM'er M1 og M2, spørger ækvivalensspørgsmålet, om L(M1) = L(M2), hvor L(M) repræsenterer det sprog, der genkendes af TM M.
Det generelle problem med at bestemme ækvivalensen af to TM'er vides ikke at kunne afgøres. Det betyder, at der ikke er nogen algoritme, der altid kan afgøre, om to vilkårlige TM'er genkender det samme sprog eller ej. Dette resultat blev bevist af Alan Turing i hans banebrydende arbejde om beregningsevne.
Det er dog vigtigt at bemærke, at dette resultat gælder for det generelle tilfælde af vilkårlige TM'er. I det specifikke tilfælde, hvor begge TM'er beskriver afgørelige sprog, bliver ækvivalensspørgsmålet afgørligt. Dette skyldes, at afgørelige sprog er dem, for hvilke der findes en TM, der kan bestemme medlemskab af sproget. Derfor, hvis to TM'er beskriver afgørelige sprog, kan vi konstruere en ny TM, der bestemmer deres ækvivalens.
For at illustrere dette, lad os overveje et eksempel. Antag, at vi har to TM'er M1 og M2, der beskriver afgørelige sprog. Vi kan konstruere en ny TM M, der bestemmer deres ækvivalens som følger:
1. Givet en indgang x, simuler M1 på x og M2 på x samtidigt.
2. Hvis M1 accepterer x og M2 accepterer x, så accepter.
3. Hvis M1 afviser x og M2 afviser x, så accepter.
4. Ellers afvis.
Ved konstruktion vil TM M acceptere et input x, hvis og kun hvis både M1 og M2 accepterer x, eller både M1 og M2 afviser x. Dette betyder, at M bestemmer ækvivalensen af M1 og M2 for enhver given input x.
Mens det generelle problem med at bestemme ækvivalensen af to vilkårlige TM'er er uafgørligt, hvis TM'erne beskriver afgørelige sprog, bliver ækvivalensspørgsmålet afgøreligt. Dette skyldes, at afgørelige sprog kan bestemmes af en TM, hvilket giver os mulighed for at konstruere en TM, der bestemmer deres ækvivalens. Afgøreligheden af ækvivalensspørgsmålet for TM'er, der beskriver afgørelige sprog, giver vigtig indsigt i disse sprogs beregningsmæssige kompleksitet.
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?
- 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?
- Beskriv processen med at transformere en Turing-maskine til et sæt fliser til PCP, og hvordan disse fliser repræsenterer beregningshistorien.
Se flere spørgsmål og svar i Afgørelighed