More Intensional Versions of Rice’s Theorem

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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 languageEnglish
Title of host publicationComputing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings
EditorsBarnaby Martin, Daniël Paulusma, Giuseppe Primiero, Florin Manea
Number of pages13
PublisherSpringer
Publication date2019
Pages217-229
ISBN (Print)9783030229955
DOIs
Publication statusPublished - 2019
Event15th Conference on Computability in Europe, CiE 2019 - Durham, United Kingdom
Duration: 15 Jul 201919 Jul 2019

Conference

Conference15th Conference on Computability in Europe, CiE 2019
LandUnited Kingdom
ByDurham
Periode15/07/201919/07/2019
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11558 LNCS
ISSN0302-9743

ID: 227333975