Den vanliga datorautomaten för allmän användning (t.ex. en Turingmaskin) är logiskt irreversibel – dess övergångsfunktion saknar ett endavärde omvänt. Här visas att sådana maskiner kan göra logiskt reversibla i varje steg, samtidigt som de behåller sin enkelhet och sin förmåga att göra allmänna beräkningar. Detta resultat är av stort fysiskt intresse eftersom det gör det rimligt att det finns termodynamiskt reversibla datorer som kan utföra användbara beräkningar med användbar hastighet samtidigt som de försvinner betydligt mindre än kT av energi per logiskt steg. I det första skedet av sin beräkning är den logiskt reversibla automaton parallell med motsvarande irreversibla automaton, förutom att den sparar alla mellanliggande resultat och därigenom undviker den irreversibla driften av radering. Det andra steget består av att skriva ut önskad utgång. Det tredje steget förfogar sedan reversibelt över alla oönskade mellanliggande resultat genom att retracing stegen i det första steget i bakåt ordning (en process som är endast möjlig eftersom det första steget har utförts reversibelt), och därmed återställa maskinen (med undantag för den nu skrivna utdatabandet) till sitt ursprungliga skick. Den slutliga maskinkonfigurationen innehåller alltså önskad utgång och en rekonstruerad kopia o f inmatningen, men inga andra oönskade data. Ovanstående resultat visas explicit med hjälp av en typ av tre-tape Turing maskin. Biosyntesen av budbärarRNA diskuteras som ett fysiskt exempel på reversibel beräkning. Det vanliga digitala datorprogrammet utför ofta operationer som verkar kasta bort information om datorns historia och lämnar maskinen i ett tillstånd vars omedelbara föregångare är tvetydig. Sådana transaktioner inkluderar radering eller överskrivning av data, och inträde i en del av programmet som behandlas av flera olika överföringsinstruktioner. Med andra ord, den typiska datorn är logiskt irreversibel - dess övergångsfunktion (den partiella funktion som kartlägger varje hel maskin stat på sin efterträdare, om staten har en efterträdare) saknar en enda värderad invers. Landauer [I] har ställt frågan om huruvida logisk irreversibilitet är ett oundvikligt inslag i användbara datorer och argumenterat för att det är, och har visat den fysiska och filosofiska betydelsen av denna fråga genom att visa att när en fysisk dator kastar bort information om sitt tidigare tillstånd måste den generera en motsvarande mängd entropi. Därför måste en dator upplösa minst kTln 2 av energi (ca 3 X 10 "" joule i rumstemperatur) för varje bit av information som den raderar eller på annat sätt kastar bort. En irreversibel dator kan alltid göras reversibel genom att den sparar all information den annars skulle kasta bort. Till exempel kan maskinen få ett extra band (initialt tomt) på vilket den kunde spela in varje operation som den utfördes, tillräckligt detaljerat för att det föregående tillståndet skulle vara unikt bestämt av det nuvarande tillståndet och den sista skivan på bandet. Men som Landauer påpekade skulle detta bara skjuta upp problemet med att kasta bort oönskad information, eftersom bandet måste raderas innan det kan återanvändas. Det är därför rimligt att kräva av en användbar reversibel dator att den, om den stannar, skulle ha raderat alla sina mellanliggande resultat, vilket bara lämnar efter sig den önskade utmatningen och den ursprungligen möblerade inmatningen. (Maskinen måste tillåtas att spara sin ingång på annat sätt den inte kunde vara reversibel och fortfarande utföra beräkningar där indata inte var unikt bestäms av utdata.) Vi kommer att visa att reversibla datorer för allmän användning (Turneringsmaskiner) som uppfyller dessa krav verkligen existerar, och att de inte behöver vara mycket mer komplicerade än de irreversibla datorer på vilka de är mönstrade. Beräkningar på en vändbar dator tar ungefär dubbelt så många steg som på en vanlig och kan kräva en stor mängd tillfällig lagring. Innan vi går vidare med den formella demonstrationen kommer argumentet att föras igenom på den nuvarande heuristiska nivån. USA:s beskydd. Atomenergikommissionen medan författaren var anställd *En stor del av det arbete om fysisk reversibilitet som rapporterades i detta dokument utfördes av Argonne National Lsboratory, Argonne, Illinois. 525 Vi börjar med den reversibla men ody dator som nämnts tidigare, som har producerat, och misslyckats med att radera, en lång historia av sin verksamhet. Nu, en band full av slumpmässiga data kan inte raderas utom genom en irreversibel process: men, historiebandet är inte slumpmässig-det finns en subtil ömsesidig redundans mellan den och maskinen som producerade den, som kan utnyttjas för att radera den reversibelt. Till exempel, om man i slutet av beräkningen började använda den ursprungliga övergångsfunktionen på ett nytt stadium, skulle maskinen börja utföra hela beräkningen bakåt och så småningom återföra historietejpen till sitt ursprungliga blanktillstånd [2]. Eftersom framåtberäkningen var deterministisk och reversibel, skulle också det bakre stadiet vara. Tyvärr skulle det bakåtgående skedet omvandla utdata tillbaka till den ursprungliga indatan, vilket gör den totala beräkningen helt värdelös. Förstöring av den önskade utmatningen kan förhindras helt enkelt genom att göra en extra kopia av den på ett separat band, efter det främre stadiet, men före det bakre stadiet. Under denna kopieringsoperation (som kan göras reversibelt om bandet som används för kopian inledningsvis är tomt) avbryts inspelningen av historiebandet. Det bakre stadiet kommer då att förstöra endast originalet och inte kopian. I slutet av komputationen kommer datorn att innehålla den (rekonstruerade) ursprungliga indatan plus den intakta kopian av utdatan; all annan lagring kommer att ha återställts till sitt ursprungliga blanktillstånd. Även om ingen historia finns kvar, är beräkningen reversibel och deterministisk, eftersom vart och ett av dess stadier har varit så. En nackdel med den reversibla maskinen verkar vara den stora mängd tillfällig lagring som behövs för historien-för ett v-steg första steget, v rekord av historia skulle behöva skrivas. I ett senare avsnitt kommer det att hävdas att genom att utföra ett arbete i många steg snarare än bara tre, kan den nödvändiga mängden tillfällig lagring ofta minskas avsevärt. I det sista avsnittet diskuteras möjligheten av reversibla fysiska datorer, som kan avleda mindre än kT energi per steg, med hjälp av exempel från den biokemiska apparaten i den genetiska koden. Detta avsnitt formaliserar argumentet i föregående avsnitt genom att visa att, med tanke på en vanlig Turing maskin S, man kan bygga en reversibel tre-tape Turing maskin R, som emulerar S på någon standard ingång, och som lämnar efter sig, i slutet av sin beräkning, endast den inmatning och önskad utgång. R-maskinens beräkning fortskrider med tre steg som beskrivs ovan, den tredje etappen som tjänar till att göra sig av med den historia som producerades av den första. Resten av detta avsnitt får hoppas över av dem som inte är intresserade av detaljerna i beviset. 526 Den vanliga typen av ett band Turing maskin [3] består av en styrenhet, en readlwrite huvud, och en oändlig tejp uppdelad i rutor. Dess beteende styrs av en ändlig uppsättning övergångsformler (vanligtvis kallade kvintuples) av skriv-write-shift typ. Kvintuplen har formen A T --z T 'cr A', (1) vilket innebär att om styrenheten är i tillstånd A och huvudet skannar bandsymbolen T, kommer huvudet först skriva T' i stället för T ; då kommer det att skifta vänster en kvadrat, höger en kvadrat, eller förbli där det är, enligt värdet av w(-, +, eller 0, respektive); slutligen styrenheten kommer att återgå till tillstånd A ". I den vanliga generaliseringen till n-tape maskiner, T, T, och (T är alla n-tuples i kvintuple. Varje kvintupel definierar en (partiell) en-till-en kartläggning av det nuvarande helmaskinstillståndet (Le., bandinnehåll, huvudpositioner och kontrolltillstånd) på sin efterträdare och som sådan är deterministisk och reversibel. Därför kommer en Turing maskin att vara deterministisk om och endast om dess kvintuples har icke-överlappande domäner, och kommer att vara reversibel om och endast om de har icke-överlappande intervall. Den förra garanteras vanligtvis genom att kräva att delen till vänster om pilen är olika för varje quintuple. Å andra sidan är den vanliga Turingmaskinen inte vändbar. Genom att göra en Turing maskin reversibel, måste vi lägga till övergångar som nära liknar inverserna av de övergångar som den redan har. Men eftersom skriv- och skiftoperationerna inte pendlar, är omvänt av en skriv-shift kvintuple, även om den existerar, av en annan typ, nämligen skift-read-write. Vid konstruktion av en reversibel maskin är det nödvändigt att inkludera kvintuples av båda typerna, eller annars att använda en formalism där övergångar och deras inverser har samma form. Här den senare metoden tas - den reversibla maskinen kommer att använda en enklare typ av övergångsformel där, under en given övergång, varje band utsätts för en read-write eller en skiftning operation men inget band utsätts för båda. DeJnition: En fyrhörning (för en n-tape Turing maskin med ett huvud per band) är ett uttryck för den form där A och A' är positiva heltal (beskrivande interna tillstånd kontrollenheten före och efter övergången, respektive); varje t, kan vara antingen ett positivt heltal betecknande en symbol som måste läsas på kth band eller en solidus ( / ), vilket indikerar att kth band inte läses under övergången; varje t,'är antingen ett positivt heltal som anger symbolen som ska skrivas på kth band eller en medlem av uppsättningen (--, 0, +) som anger en vänster, noll, eller höger skiftning av kth band huvudet. t k = /. Maskinen skriver alltså på ett band om och endast om den just har läst det, och byter ett band endast om det inte bara har läst det. I likhet med kvintupler definierar kvadrupler kartläggningar av hela maskintillståndet som är en-till-ett. Alla readwrite-shift quintuple kan delas upp i en read-write och ett skift, båda uttrycks som fyrdubblar. Till exempel är quintuple (1) ekvivalent med par av fyrdubblar där A" är en ny kontroll-enhet staten skiljer sig från A och A ". När flera kvintuples är så split, en annan anslutningstillstånd A" måste användas för varje, för att undvika att införa obestämdhet. Fyrdubblar har följande ytterligare viktiga egenskaper, som kan kontrolleras genom inspektion. Låta vara två n-tejp fyrdubblar. 1 ) a och p är ömsesidigt inversa (definiera inversa kartläggningar av hela maskintillståndet) om och endast om A = B' och B = A'och, för varje k, antingen ( t, = 11, = / och t,'= -14,') eller (tk # / och t,' = 14, och t, = u,'). Inversen av en fyrdubbla, med andra ord, erhålls genom att interchange det initiala kontrolltillståndet med finalen, läsbandssymbolerna med de skrivna, och ändra tecken på alla skift. 2 ) Områdena för a och p överlappar om och endast om A = B och, för varje k, ( t, = j eller ulC = / eller t, = 14,). Att inte överlappa domänerna kräver ett annorlunda initialt kontrolltillstånd eller en annorlunda skannad symbol på en del band som läses av båda fyrdubblar. 3 ) Områdena för a och p överlappar om och endast om A' = B' och, för varje k, ( t, = I eller u, = I eller t,' = u,"). Egenskapen är jämförbar med den tidigare, men beror på det slutliga kontrolltillståndet och de skrivna bandsymbolerna. En reversibel, deterministisk n-tape Turingmaskin kan nu definieras som en ändlig uppsättning n-tape fyrdubblar, av vilka två inte överlappar vare sig i domän eller räckvidd. Vi vill nu visa att sådana maskiner kan tillverkas för att efterlikna vanliga (oreversibel) Turingmaskiner. Det är praktiskt att ålägga maskinerna att efterlikna vissa format-standardiseringskrav, som dock inte avsevärt begränsar deras datorkraft [ 4 ]. Definition: En inmatning eller utmatning sägs vara standard när den är på annars tomma band och innehåller inga inbäddade luckor, när bandhuvudet skannar den tomma kvadraten omedelbart till vänster om den, och när den endast innehåller bokstäver som hör till band alfabetet av maskinen skannar den. och kontroll stater A, och A, visas i ingen annan kvintuple. Dessa två är alltså de första respektive sista som utförs i varje avslutande beräkning på en standardinmatning. Bokstaven b representerar ett blanktecken. Frasen "maskin M, givet standard indatasträng I, beräknar standard utdatasträngen P" kommer att förkortas M: I -+ P. För en n-tape maskin kommer detta att bli M: (Il; I,;.... ; I,) -+ ( P, ; P,. ; P,), där jag och P, är standardinmatningen och standardutgången på kth-bandet. Ett tomt band kommer att förkortas B. Den huvudsakliga teorem kan nu anges: Theorem: För varje standard ett-tape Turing maskin S, finns det en tre-tape reversibel, deterministisk Turing maskin R sådan att om jag och P är strängar på alfabetet S, som innehåller inga inbäddade luckor, S stannar på I om och endast om R stannar på (I ; B ; B ), och S: I - + P om och endast omR: (I; B ; R ) -+ (I; B ; P ). Dessutom, om S har f kontroll tillstånd, N kvintuples och ett band alfabet z bokstäver, inklusive blank, R kommer att ha 2f+ 2 N + 4 stater, 4 N + 2z + 3 fyrdubblar och band alfabet z, N + 1, och z bokstäver, respektive. Slutligen, om i en viss beräkning S kräver u steg och använder s kvadrater av tejp, producerar en utgång av längd A, då R kommer att kräva 4v + 4A + 5 steg, och använda s, u + 1, och A + 2 kvadrater på sina tre band, respektive. (Det kommer senare att hävdas att om u>>> s kan det totala rymdbehovet minskas till mindre än 2 6.) Proofi För att konstruera maskinen R börjar vi med arrangEach kvintuple bryts nu in i ett par fyrdubblar med N kvintuples av S i någon ordning med de stanas beskrivs tidigare. Mth kvintuple blir dard kvintuples först och sist: Den nytillkomna stater A,!" skiljer sig från de gamla staterna och från varandra: varje A" visas endast i ett (9) par fyrdubblar. Tabell 1 Struktur och drift av en tre-tape vändbar Turingmaskin. Beräkningen fortskrider i tre steg med hjälp av olika uppsättningar av fyrdubblar och kontrolltillstånd, koppling som sker genom tillstånd A, och C,,. Till höger visas bandens innehåll symboliskt i början och slutet av varje steg. Understången betecknar huvudets posltlon. Det initiala tillståndet är A och, för en avslutande beräkning, C, är det slutliga tillståndet. Innehåll o j band Arbetshistorik
Bennet's klassiska papper REF studerade idén om en vändbar Turing maskin.
Logical reversibility of computation
{'venue': None, 'journal': 'Ibm Journal of Research and Development', 'mag_field_of_study': ['Computer Science']}