More Intensional Versions of Rice’s Theorem

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedings

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.

OriginalsprogEngelsk
TitelComputing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings
RedaktørerBarnaby Martin, Daniël Paulusma, Giuseppe Primiero, Florin Manea
Antal sider13
ForlagSpringer
Publikationsdato2019
Sider217-229
ISBN (Trykt)9783030229955
DOI
StatusUdgivet - 2019
Begivenhed15th Conference on Computability in Europe, CiE 2019 - Durham, Storbritannien
Varighed: 15 jul. 201919 jul. 2019

Konference

Konference15th Conference on Computability in Europe, CiE 2019
LandStorbritannien
ByDurham
Periode15/07/201919/07/2019
NavnLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vol/bind11558 LNCS
ISSN0302-9743

ID: 227333975