Turing-complet

Résumé

En informatique et en logique, un système formel est dit complet au sens de Turing ou Turing-complet (par calque de l’anglais Turing-complete) s’il possède un pouvoir expressif au moins équivalent à celui des machines de Turing. Dans un tel système, il est donc possible de programmer n'importe quelle machine de Turing. Cette notion est rendue pertinente par la thèse de Church, qui postule l’existence d’une notion naturelle de calculabilité. Ainsi, le pouvoir expressif des machines de Turing coïncide avec celui des fonctions récursives, du lambda calcul, ou encore des machines à compteurs. Bien que certains modèles de calcul, appelés des hypercalculs, soient strictement plus expressifs que les machines de Turing, ces modèles sont des objets de spéculation (requérant par exemple d’effectuer une infinité d’opérations, ou de calculer sur l’ensemble des nombres réels) et l’on ignore s’ils sont physiquement réalisables. Dans ces conditions, la thèse de Church conjecture l’universalité du

Source officielle

https://fr.wikipedia.org/wiki/Turing-complet

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (51)

Publications associées

Chargement

Personnes associées (1)

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (82)

thumb|Fragment de code écrit dans le langage de programmation JavaScript. Un langage de programmation est un langage informatique destiné à formuler des algorithmes et produire des programmes informa

En informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur. Ce modèle a été imaginé par Alan Turing en 1936, en v

thumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de

Afficher plus

Concepts associés

Chargement

Cours associés (30)

Cours associés

Chargement

Séances de cours associées (32)

Afficher plus

Séances de cours associées

Chargement

This research work deals with the design of linear CMOS RF power amplifiers. Two important aspects are treated: efficiency enhancement and frequency-tunable capability. For this purpose, two different integrated circuits were realized in a 0.11 µm technology, each one addressing a different aspect. With respect to efficiency enhancement, a dynamic supply RF power amplifier was realized. The circuit was designed for an operating frequency of 5.2 GHz, but measurements were also performed at 2.4 GHz. The integrated circuit includes a class A amplifier and a high-efficiency, switched-mode modulator. It occupies an area of 1.35 mm2. Two-tone measurement results at 2.4 and 5.2 GHz showed that the system can deliver over 16 dBm (40 mW) linear output power with efficiencies of 22.7% and 12.6%, respectively. Compared to a constant 2.5 V supply operation, the power amplifier operating with the dynamic supply delivers higher linear output power. Moreover, a relative efficiency improvement of a factor of 2.3 at 2.4 GHz and of a factor of 1.6 at 5.2 GHz at low output power levels is achieved. OFDM measurements at 2.4 GHz demonstrated that for an EVM lower than 3% and for an equal output power of 11 dBm (12.6 mW), the absolute improvement in efficiency is over 3.2%. In this work we also propose a tunable impedance matching network for use in multiband RF power amplifiers. This novel network is based on coupled inductors. A frequency-tunable RF power amplifier using this network was designed for operation at 3.7 and 5.2 GHz. Simulation results for the complete system integrated in a CMOS technology showed good results. However, the frequency-tunable behavior could not be observed in the characterization of the integrated circuit because of the low coupling factor of the integrated coupled inductors. A hybrid implementation using the integrated CMOS power amplifier, a discrete commercial RF transformer and a discrete bipolar transistor to control the current in the secondary winding of the transformer was carried out. The circuit was designed for operation at 200 and 300 MHz. The measurements have shown that at 200 MHz a relative improvement in efficiency of a factor of 1.4 was achieved. Moreover, less distortion was generated with the proposed tunable output matching network. The hybrid implementation allowed us to demonstrate the feasibility of the frequency-tunable RF power amplifier based on coupled inductors.

EPFL2009

Chargement

A Virtual Keyboard Based on True-3D Optical Ranging

Edoardo Charbon, Huan Du, Félix Lustenberger

In this paper, a complete system is presented which mimics a QWERTY keyboard on an arbitrary surface. The system consists of a pattern projector and a true-3D range camera for detecting the typing events. We exploit depth information acquired with the 3D range camera and detect the hand region using a pre-computed reference frame. The fingertips are found by analyzing the hands' contour and fitting the depth curve with different feature models. To detect a keystroke, we analyze the feature of the depth curve and map it back to a global coordinate system to find which key was pressed. These steps are fully automated and do not require human intervention. The system can be used in any application requiring zero form factor and minimized or no contact with a medium, as in a large number of cases in human-to-computer interaction, virtual reality, game control, 3D designs, etc.

2005

Chargement

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 execution. Assessing the remaining attack surface of an application under advanced control-flow hijack defenses such as CFI and shadow stacks remains an open problem. We introduce BOPC, a mechanism to automatically assess whether an attacker can execute arbitrary code on a binary hardened with CFI/shadow stack defenses. BOPC computes exploits for a target program from payload specifications written in a Turing-complete, high-level language called SPL that abstracts away architecture and program-specific details. SPL payloads are compiled into a program trace that executes the desired behavior on top of the target binary. The input for BOPC is an SPL payload, a starting point (e.g., from a fuzzer crash) and an arbitrary memory write primitive that allows application state corruption. To map SPL payloads to a program trace, BOPC introduces Block Oriented Programming (BOP), a new code reuse technique that utilizes entire basic blocks as gadgets along valid execution paths in the program, i.e., without violating CFI or shadow stack policies. We find that the problem of mapping payloads to program traces is NP-hard, so BOPC first reduces the search space by pruning infeasible paths and then uses heuristics to guide the search to probable paths. BOPC encodes the BOP payload as a set of memory writes. We execute 13 SPL payloads applied to 10 popular applications. BOPC successfully finds payloads and complex execution traces which would likely not have been found through manual analysis - while following the target's Control-Flow Graph under an ideal CFI policy in 81% of the cases.

ASSOC COMPUTING MACHINERY2018

Chargement

EPFL2009