Conference paper
Undecidability and temporal logic: some landmarks from Turing to the present
This is a selective survey and discussion of some of the landmark undecidability results in temporal logic, beginning with Turing's undecidability of the Halting problem which, in retrospect, can be regarded as the historically first undecidability result for a suitable temporal logic over configuration graphs of Turing machines.
I will discuss some of the natural habitats of undecidable temporal logics, such as first-order, interval-based and real time temporal logics, as well as some extensions that often lead to undecidability, such as two-dimensional temporal logics and temporal-epistemic logics.
Language: | English |
---|---|
Year: | 2012 |
Pages: | 3-4 |
Proceedings: | 19th International Symposium on Temporal Representation and Reasoning (TIME 2012)International Symposium on Temporal Representation and Reasoning |
ISBN: | 0769548024 , 1467326593 , 9780769548029 and 9781467326599 |
ISSN: | 23326468 and 15301311 |
Types: | Conference paper |
DOI: | 10.1109/TIME.2012.26 |
Cognition Complexity theory Computer science Educational institutions Encoding Real-time systems Turing machines Turing machines configuration graphs Turing undecidability computability first-order logic graph theory interval-based logic landmark undecidability real time temporal logics temporal logic temporal logics temporal-epistemic logics two-dimensional temporal logics undecidability undecidable temporal logics