Vi presenterar en ram för verifierad programmering av multi-tape Turing maskiner i Coq. Bättre på tidigare arbete av Asperti och Ricciotti i Matita, implementerar vi flera lager av abstraktion. Det högsta skiktet gör det möjligt för en användare att implementera icke-triviala algoritmer som Turing maskiner och verifiera deras korrekthet, samt tid och utrymme komplexitet komposition. Användaren kan göra det utan att någonsin nämna tillstånd, symboler på band eller övergångsfunktioner: De skriver program på ett tvingande språk med register som innehåller värden av kodbara datatyper, och vårt ramverk konstruerar motsvarande Turing maskiner. Som fallstudier verifierar vi en översättning från multi-tape till en-tape maskiner samt en universell Turing maskin, både med polynom tid overhead och konstant faktor utrymme overhead.
Forster, Kunze och Wuttke minskar problemet med multi-tape Turing maskiner till ett band Turing maskiner REF.
Verified programming of Turing machines in Coq
{'venue': 'CPP 2020', 'journal': None, 'mag_field_of_study': ['Computer Science']}