Quantum logic

AutomatonlogicM.SchallerandK.SvozilInstitutf¨urTheoretischePhysik,TechnischeUniversit¨atWienWiednerHauptstraße8-10/136,A-1040Vienna,Austriae-mail:[e-mail]llogicofMooreandMealytypeautomataisinvesti-gated.keywords:automatonlogic;partitionlogic;comparisontoquantumlogic;intrinsicmeasurements1Introduction1.1MotivationAlreadyin1956,Moore[20]presentedanexplicitexampleofafour-stateautoma-tonfeaturingan“automatonuncertaintyprinciple”ataveryelementarylevel.TheformalismintroducedbyMoorehasbeenextendedbyConway[6]andChaitin[5],amongothers.See[14,4]forarecentreviewonMooreandMealyautomata.Inanarticleentitled“computationalcomplementarity”,D.FinkelsteinandS.R.Finkelstein[8]werethefirsttostudytheexperimentallogicofverygen-eralautomata;i.e.,theorderedstructureofpropositionsarisingfromexperimentsonautomata,andtherelationshiptoquantumphysics.Basedonthisresearch,GribandZapatrin[11,12]investigatedanautomatontype,whosecorrespond-ing“macrostatements”(propositionsaboutautomatonensembles),modelarbi-traryorthomodularlattices[13].Inanotherinterestingdevelopment,Crutchfield[7]describedthemeasurementprocessbyintroducingahierarchyofautomata.1ThisarticlegoesbacktoMoore’soriginalapproachanddealswithanalge-braiccharacterizationoftheexperimentallogicofMooreandMealytypeau-tomata.1.2ClassicallogicversusquantumlogicversusautomatonlogicInthefollowinf,weshalldescribe,inasomewhatsimplifiedstyle,theconstruc-tionofthelogiccalculusofclassicalphysicalsystems,quantumsystemsandau-tomata.LetSbeaclassicalsystem.Wedenotethesetofallobservablesofthesystemby(Ai)i∈I.Itischaracteristicforclassicalsystemsthatall(Ai)i∈Iaresimultane-ouslymeasurable.Wedenotetheoutcomeofsuchameasurementby(xi)i∈I.ThesetofallpossibleoutcomesformstheobservationspaceO.ThemostgeneralformofapredictionconcerningSisthatthepoint(xi)i∈Ideterminedbyactuallymeasuring(Ai)i∈I,willlieinasubsetSofO.WemaycallthesubsetsofOthe“experimentalpropositions”concerningS.ThesesubsetsformaBooleanalgebra(whichisequaltothepowersetofO).AssociatedwiththesystemSisthephasespaceΓ.Accordingtotheconceptofaphasespace,thestateofSisrepresentedbyapointp∈Γ,whichdeterminestheoutcomeofthemeasurements(Ai)i∈Iinadeterministicway.Wemayassumeamappingf:Γ→O,whichdescribesthiscorrespondence.EachexperimentalpropositionScorrespondstoasubsetΓSofΓbyΓS=f−1(S).ThesesubsetsΓSformthepropositionalcalculusofthesys-temS,whichisalsoaBooleanalgebra[usingf−1(S∪T)=f−1(S)∪f−1(T),f−1(S∩T)=f−1(S)∩f−1(T)andf−1(S0)=(f−1(S))0].Thesituationinquantummechanicsisasfollows.LetSbeaquantumsystemandlet(Bj)j∈Jbeasetofcompatiblemeasurements.Theexperimentalproposi-tionsconcerningthemeasurementof(Bj)j∈JareagainsubsetsoftheobservationspaceOJofallpossibleoutcomes(xj)j∈J(now,OJdependsontheset(Bj)j∈J).Accordingtothequantummechanicalformalism,thesubsetsΓSofthephasespaceΓhavetobereplacedbyclosedsubspacesofanappropriateHilbertspaceH(orequivalently,byprojectionsoperatorspSofH).ThesetL(H)ofallclosedsubspacesiscalledthepropositionalcalculus(quantumlogic)ofthesystemS.L(H)formsacompleteatomisticorthomodularlattice(cf.[17,23,24]).ThestoryofquantumlogicgoesbacktotheseminalpaperofBirkhoffandvonNeumann[1].TheinterestinquantumlogicwasrevivedthroughtheinvestigationsofJauch[16]andPiron[22].Thehistoricaldevelopmentandthedifferentapproachestoquantumlogiccanbefoundin[15].2Atlastweturntoautomatalogic.Anautomaton(MealyorMooreautomaton)isafinitedeterministicsystemwithinputandoutputcapabilities.AtanytimetheautomatonisinastateqofafinitesetofstatesQ.Thestatedeterminesthefutureinput–outputbehavioroftheautomaton.Ifaninputisapplied,theautomatonas-sumesanewstate,dependingbothontheoldstateandontheinput.Anoutputisemittedwhichdependsontheoldstateandtheinput(Mealyautomaton)oronlyonthenewstate(Mooreautomaton).Automatonexperimentsareconductedbyapplyinganinputsequenceandobservingtheoutputsequence.Theautomatonistherebytreatedasablackboxwithknowndescriptionbutunknowninitialstate.LetEbeanautomatonexperimentandletOEbetheobservationspace,i.e.,OEisthesetofallpossibleoutcomesofE.Becauseofthedeterministicnatureoftheautomaton,foreveryexperimentEthereexistsamappingλE:Q→OE,de-terminingtheoutcomeofE,anddependingontheinitialstateoftheautomaton.Asintheclassicalandquantumcase,experimentalpropositionsconcerningtheexperimentEaresubsetsSEofOE.ForeveryexperimentE,theinverseimagesofthesetsSEunderλEformsaBooleanalgebra(moreexactly,afieldofsets).TheelementsofthisBooleanalgebraaresubsetsofthestatesetQ.Weobtainapropositionalcalculus,termedtheautomatonlogic,ifwe“paste”allBooleanal-gebrascorrespondingtoallexperimentstogether.Thiscalculusformsapartitionlogic[27,25].Intuitively,ashasalreadybeenobservedbyMoore[20],itmayoccurthattheautomatonundergoesanirreversiblestatechange,i.e.,informationabouttheautomaton’sinitialstateislost.Asecond,laterexperimentmaythere-forebeaffectedbythefirstexperiment,andviceversa.Hence,bothexperimentsareincompatible.Inthissetup,theobserverhasaqualifyinginfluenceonthemea-surementresultinsofarasaparticularobservablehastobechosenamongaclassofnon-co-measurableobservables.Buttheobserv