Turing completeness

Formal sciences
Theoretical computer science
Programming language theory
Formal semantics

Related publications (13)

About
Privacy
Disclaimer

Graph Chatbot

A Toolbox for Barriers on Interactive Oracle Proofs

Alessandro Chiesa

Interactive oracle proofs (IOPs) are a proof system model that combines features of interactive proofs (IPs) and probabilistically checkable proofs (PCPs). IOPs have prominent applications in complexity theory and cryptography, most notably to constructing ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

What graph neural networks cannot learn: depth vs width

Andreas Loukas

This paper studies the expressive power of graph neural networks falling within the message-passing framework (GNNmp). Two results are presented. First, GNNmp are shown to be Turing universal under sufficient conditions on their depth, width, node attribut ...

2020

Verification of Software Network Functions with No Verification Expertise

Arseniy Zaostrovnykh

Software network functions (NFs), such as a network address translator, load balancer, or proxy, promise to bring flexibility and rapid innovation to computer networks and to reduce operational costs. However, continuous updates and flexibility typically c ...

EPFL2020

Block Oriented Programming: Automating Data-Only Attacks

Mathias Josef Payer

With the widespread deployment of Control-Flow Integrity (CFI), control-flow hijacking attacks, and consequently code reuse attacks, are significantly more difficult. CFI limits control flow to well-known locations, severely restricting arbitrary code exec ...

ASSOC COMPUTING MACHINERY2018

Network Flow Integer Programming to Track Elliptical Cells in Time-Lapse Sequences

Pascal Fua, Engin Türetken, Xinchao Wang, Carlos Joaquin Becker

We propose a novel approach to automatically tracking elliptical cell populations in time-lapse image sequences. Given an initial segmentation, we account for partial occlusions and overlaps by generating an over-complete set of competing detection hypothe ...

Institute of Electrical and Electronics Engineers2017

Indicators of Evidence for Bioequivalence

Stephan Morgenthaler, Robert Staudte

Some equivalence tests are based on two one-sided tests, where in many applications the test statistics are approximately normal. We define and find evidence for equivalence in Z-tests and then one-and two-sample binomial tests as well as for t-tests. Mult ...

Mdpi Ag2016

The Programmable Logic-in-Memory (PLiM) Computer (Invited)

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù, Anupam Chattopadhyay

Realization of logic and storage operations in memristive circuits have opened up a promising research direction of in-memory computing. Elementary digital circuits, e.g., Boolean arithmetic circuits, can be economically realized within memristive circuits ...

Ieee2016

FPGAs for the Masses: Affordable Hardware Synthesis from Domain-Specific Languages

Nithin George

Field Programmable Gate Arrays (FPGAs) have the unique ability to be configured into application-specific architectures that are well suited to specific computing problems. This enables them to achieve performances and energy efficiencies that outclass oth ...

EPFL2016

An overview of the Leon verification system: verification by translation to recursive functions

Viktor Kuncak, Etienne Kneuss, Philippe Paul Henri Suter, Régis William Blanc

We present the Leon verification system for a subset of the Scala programming language. Along with several functional features of Scala, Leon supports imperative constructs such as mutations and loops, using a translation into recursive functional form. Bo ...

2013

Limits Of Metabelian Groups

Luc Guyot

We describe the two-generated limits of abelian-by-(infinite cyclic) groups in the space of marked groups using number theoretic methods. We also discuss universal equivalence of these limits. ...

2012

Page 1 of 2

2012