Zobrazeno 1 - 10
of 33
pro vyhledávání: '"Theory of computation → Constructive mathematics"'
Autor:
Kirst, Dominik, Peters, Benjamin
Gödel published his groundbreaking first incompleteness theorem in 1931, stating that a large class of formal logics admits independent sentences which are neither provable nor refutable. This result, in conjunction with his second incompleteness th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3f6f63d6692e730f0e796daaaa47f5f6
Autor:
Forster, Yannick, Jahn, Felix
Publikováno v:
CSL 2023-31st EACSL Annual Conference on Computer Science Logic
CSL 2023-31st EACSL Annual Conference on Computer Science Logic, Feb 2023, Warsaw, Poland. pp.1-21, ⟨10.4230/LIPIcs.CSL.2023.16⟩
CSL 2023-31st EACSL Annual Conference on Computer Science Logic, Feb 2023, Warsaw, Poland. pp.1-21, ⟨10.4230/LIPIcs.CSL.2023.16⟩
We present a constructive analysis and machine-checked theory of one-one, many-one, and truth-table reductions based on synthetic computability theory in the Calculus of Inductive Constructions, the type theory underlying the proof assistant Coq. We
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::946ee401f212ea08e8915ea1c939837c
Autor:
Cohen, Liron, Rahli, Vincent
The principle of continuity is a seminal property that holds for a number of intuitionistic theories such as System T. Roughly speaking, it states that functions on real numbers only need approximations of these numbers to compute. Generally, continu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ea78d5d33ad1734a2bf3689126e17434
Autor:
Nandakumar, Satyadev, Pulari, Subin
Publikováno v:
Theory of Computing Systems.
We initiate the study of effective pointwise ergodic theorems in resource-bounded settings. Classically, the convergence of the ergodic averages for integrable functions can be arbitrarily slow [Ulrich Krengel, 1978]. In contrast, we show that for a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1e5515ce56ea3a6bbc85ae736623ca63
https://doi.org/10.1007/s00224-022-10094-9
https://doi.org/10.1007/s00224-022-10094-9
Publikováno v:
ITP 2022-13th International Conference on Interactive Theorem Proving
ITP 2022-13th International Conference on Interactive Theorem Proving, Aug 2022, Haifa, Israel
ITP 2022-13th International Conference on Interactive Theorem Proving, Aug 2022, Haifa, Israel
We present a generalised, constructive, and machine-checked approach to Kolmogorov complexity in the constructive type theory underlying the Coq proof assistant. By proving that nonrandom numbers form a simple predicate, we obtain elegant proofs of u
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::268963f77c934d4e10796f788240596f
https://inria.hal.science/hal-03596267
https://inria.hal.science/hal-03596267
Autor:
Hermes, Marc, Kirst, Dominik
Tennenbaum’s theorem states that the only countable model of Peano arithmetic (PA) with computable arithmetical operations is the standard model of natural numbers. In this paper, we use constructive type theory as a framework to revisit and genera
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::786737b0c0d47cd377d0f892fc4c97b2
Autor:
Kirst, Dominik
The back-and-forth method is a well-known technique to establish isomorphisms of countable structures. In this proof pearl, we formalise this method abstractly in the framework of constructive type theory, emphasising the computational interpretation
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6482e12c39d58a169d5cf62a58e12227
This paper discusses the formalization of synthetic cohomology theory in a cubical extension of Agda which natively supports univalence and higher inductive types. This enables significant simplifications of many proofs from Homotopy Type Theory and
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b4c92e64fa3e04c955b7016eab8c5850
LIPIcs, Volume 239, TYPES 2021, Complete Volume
LIPIcs, Vol. 239, 27th International Conference on Types for Proofs and Programs (TYPES 2021), pages 1-280
LIPIcs, Vol. 239, 27th International Conference on Types for Proofs and Programs (TYPES 2021), pages 1-280
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::00d359b583282ae2aa69c7ee4365d6e3
https://drops.dagstuhl.de/opus/volltexte/2022/16768/
https://drops.dagstuhl.de/opus/volltexte/2022/16768/
Front Matter, Table of Contents, Preface, Conference Organization
LIPIcs, Vol. 239, 27th International Conference on Types for Proofs and Programs (TYPES 2021), pages 0:i-0:viii
LIPIcs, Vol. 239, 27th International Conference on Types for Proofs and Programs (TYPES 2021), pages 0:i-0:viii
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::65f9d5c5c9c15db7bc7df8eac5c02f6e