I den här artikeln undersöker vi den logiska strukturen hos minnesmodeller av teoretiskt och praktiskt intresse. Vårt huvudsakliga intresse ligger i "logiken bakom en fast minnesmodell" snarare än i "en modell av något slag bakom ett givet logiskt system". Som ett effektivt språk för resonemang om sådana minnesmodeller använder vi separationslogikens formalism. Vårt huvudsakliga resultat är att för varje konkret val av högliknande minnesmodell är validiteten i den modellen obeslutbar även för rent propositionella formler på detta språk. Den viktigaste nyheten med vår syn på problemet är att vi fokuserar på giltighet i specifika, konkreta minnesmodeller, i motsats till giltighet i allmänna modellklasser. Förutom sitt inneboende tekniska intresse ger detta resultat också nya insikter om arten av deras decedable fragment. Framför allt visar vi att för att erhålla sådana decibelt fragment måste antingen formelspråket vara kraftigt begränsat eller värderingen av propositionsvariabler begränsas. Dessutom visar vi att ett antal propositionssystem som ungefärlig separationslogik också är obeslutbara. I synnerhet löser detta de öppna problemen med beslutbarhet för Booleska BI och Klassiska BI. Dessutom tillhandahåller vi ett av de enklaste obeslutbara propositionssystem som för närvarande är kända i litteraturen, som kallas "Minimal Boolesk BI", genom att kombinera det rent positiva implikationskonjunkturfragmentet av boolesk logik med lagarna om multiplikativ * -konjunktion, dess enhet och dess angränsande implikation, som ursprungligen tillhandahölls av intuitionistisk multiplikativ linjär logik. Var och en av dessa två komponenter är individuellt decidable: implikation-konjunktur fragment av boolesk logik är co-NP-fullständig, och intuitionistisk multiplicativ linjär logik är NP-fullständig. Alla våra obeslutbara resultat uppnås med hjälp av en direkt kodning av Minsky-maskiner.
Här rapporterar vi om den huvudsakliga utvecklingen i litteraturen relaterad till våra obeslutbara resultat, både före och efter deras ursprungliga publicering i REF.
Undecidability of Propositional Separation Logic and Its Neighbours
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}