3 years ago

Refining Properties of Filter Models: Sensibility, Approximability and Reducibility.

Flavien Breuvart

In this paper, we study the tedious link between the properties of sensibility and approximability of models of untyped {\lambda}-calculus. Approximability is known to be a slightly, but strictly stronger property that sensibility. However, we will see that so far, each and every (filter) model that have been proven sensible are in fact approximable. We explain this result as a weakness of the sole known approach of sensibility: the Tait reducibility candidates and its realizability variants. In fact, we will reduce the approximability of a filter model D for the {\lambda}-calculus to the sensibility of D but for an extension of the {\lambda}-calculus that we call {\lambda}-calculus with D-tests. Then we show that traditional proofs of sensibility of D for the {\lambda}-calculus are smoothly extendable for this {\lambda}-calculus with D-tests.

Publisher URL: http://arxiv.org/abs/1801.05153

DOI: arXiv:1801.05153v1

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.