Vi undersöker möjligheten att avgöra genomförbarhetsproblemet för tvingande program med avgränsade slingor. Ett program kallas genomförbart om alla värden den beräknar är polynomiskt avgränsade i termer av indata. Genomförbarhetsproblemet är representativt för en grupp av relaterade egenskaper, som den polynomiska tidskomplexiteten. Det är välkänt att sådana egenskaper är obeslutbara för ett Turing-komplett programmeringsspråk. De kan dock vara avgörande för språk som inte är Turing-fullständiga. Men om dessa språk är tillräckligt uttrycksfulla, utgör de en utmaning för analysen. Vi är intresserade av att spåra kanten av decisionability för genomförbarhetsproblem och liknande problem. I tidigare arbete har vi visat att sådana problem är avgörande för ett språk där slingor är avgränsade men obestämda (dvs, slingorna kan gå ut innan den givna iterationen räknas). I den här artikeln tar vi hänsyn till bestämda slingor. Ett andra språkdrag som vi skiljer oss åt på är det slags uppdragsförklaringar. Med ett vanligt uppdrag visar vi att vi inte kan bestämma oss för ett mycket litet språkfragment. Vi bevisar också obeslutbarhet med förlusttilldelning (dvs. uppdrag där den modifierade variabeln kan få vilket värde som helst som begränsas av det givna uttrycket, till och med noll). Men vi bevisar att det går att bestämma med max uppdrag (dvs. uppdrag där den modifierade variabeln aldrig minskar sitt värde).
När det gäller behovet av dessa förenklingar visade REF att man inte kunde bestämma sig för ett språk som bara kan göra tillägg och bestämda slingor (som inte kan avslutas på ett tidigt stadium).
ON THE EDGE OF DECIDABILITY IN COMPLEXITY ANALYSIS OF LOOP PROGRAMS∗
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}