More Intensional Versions of Rice’s Theorem
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
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.
Original language | English |
---|---|
Title of host publication | Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings |
Editors | Barnaby Martin, Daniël Paulusma, Giuseppe Primiero, Florin Manea |
Number of pages | 13 |
Publisher | Springer |
Publication date | 2019 |
Pages | 217-229 |
ISBN (Print) | 9783030229955 |
DOIs | |
Publication status | Published - 2019 |
Event | 15th Conference on Computability in Europe, CiE 2019 - Durham, United Kingdom Duration: 15 Jul 2019 → 19 Jul 2019 |
Conference
Conference | 15th Conference on Computability in Europe, CiE 2019 |
---|---|
Land | United Kingdom |
By | Durham |
Periode | 15/07/2019 → 19/07/2019 |
Series | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 11558 LNCS |
ISSN | 0302-9743 |
ID: 227333975