A concurrent interpretation of the law of excluded middle

Add to your list(s) Download to your calendar using vCal

• Ulrich Berger (University of Swansea)
• Friday 17 November 2017, 11:00-12:00
• Computer Science, The Sloman Lounge (UG).

If you have a question about this talk, please contact Paul Taylor.

We give a computational interpretation of the law of excluded middle as a scheme for the concurrent execution of processes. The interpretation, which takes place within the framework of realisability, involves two new logical operators: Set_n(A), allowing for n concurrent processes to realise the formula A, and A || B (‘A restricted to B’), a strengthening of the implication B → A, which is realised by a computation that is guaranteed to terminate if B holds and, in case of termination, realises A. We apply this interpretation to two examples of program extraction in computable analysis: Infinite Gray-code and matrix inversion via concurrent Gaussian elimination.

This talk is part of the Theoretical computer science seminar series.

This talk is included in these lists:

• Computer Science Departmental Series
• Computer Science Distinguished Seminars
• Computer Science, The Sloman Lounge (UG)
• Theoretical computer science seminar
• computer sience

Note that ex-directory lists are not shown.