TY - GEN
T1 - More Intensional Versions of Rice’s Theorem
AU - Moyen, Jean Yves
AU - Simonsen, Jakob Grue
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85069513483&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-22996-2_19
DO - 10.1007/978-3-030-22996-2_19
M3 - Article in proceedings
AN - SCOPUS:85069513483
SN - 9783030229955
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 217
EP - 229
BT - Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings
A2 - Martin, Barnaby
A2 - Paulusma, Daniël
A2 - Primiero, Giuseppe
A2 - Manea, Florin
PB - Springer
T2 - 15th Conference on Computability in Europe, CiE 2019
Y2 - 15 July 2019 through 19 July 2019
ER -