More Intensional Versions of Rice’s Theorem
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Classic results in computability theory concern extensional results: the behaviour of partial recursive functions rather than the programs computing them. We prove a generalisation of Rice’s Theorem concerning equivalence classes of programs and show how it can be used to study intensional properties such as time and space complexity. While many results that follow from our general theorems can - and have - been proved by more involved, specialised methods, our results are sufficiently simple that little work is needed to apply them.
Originalsprog | Engelsk |
---|---|
Titel | Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings |
Redaktører | Barnaby Martin, Daniël Paulusma, Giuseppe Primiero, Florin Manea |
Antal sider | 13 |
Forlag | Springer |
Publikationsdato | 2019 |
Sider | 217-229 |
ISBN (Trykt) | 9783030229955 |
DOI | |
Status | Udgivet - 2019 |
Begivenhed | 15th Conference on Computability in Europe, CiE 2019 - Durham, Storbritannien Varighed: 15 jul. 2019 → 19 jul. 2019 |
Konference
Konference | 15th Conference on Computability in Europe, CiE 2019 |
---|---|
Land | Storbritannien |
By | Durham |
Periode | 15/07/2019 → 19/07/2019 |
Navn | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Vol/bind | 11558 LNCS |
ISSN | 0302-9743 |
ID: 227333975