In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language. Recursively enumerable languages are known as type-0 languages in the Chomsky hierarchy of formal languages. All regular, context-free, context-sensitive and recursive languages are recursively enumerable. The class of all recursively enumerable languages is called RE. There are three equivalent definitions of a recursively enumerable language: A recursively enumerable language is a recursively enumerable subset in the set of all possible words over the alphabet of the language. A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) which will enumerate all valid strings of the language. Note that if the language is infinite, the enumerating algorithm provided can be chosen so that it avoids repetitions, since we can test whether the string produced for number n is "already" produced for a number which is less than n. If it already is produced, use the output for input n+1 instead (recursively), but again, test whether it is "new". A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) that will halt and accept when presented with any string in the language as input but may either halt and reject or loop forever when presented with a string not in the language. Contrast this to recursive languages, which require that the Turing machine halts in all cases. All regular, context-free, context-sensitive and recursive languages are recursively enumerable. Post's theorem shows that RE, together with its complement co-RE, correspond to the first level of the arithmetical hierarchy.

À 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.
Cours associés (7)
MATH-483: Gödel and recursivity
Gödel incompleteness theorems and mathematical foundations of computer science
MATH-642: Artificial Life
We will give an overview of the field of Artificial Life (Alife). We study questions such as emergence of complexity, self-reproduction, evolution, both through concrete models and through mathematica
FIN-609: Asset Pricing (2011 - 2024)
This course provides an overview of the theory of asset pricing and portfolio choice theory following historical developments in the field and putting emphasis on theoretical models that help our unde
Afficher plus
Séances de cours associées (29)
Utilité prévue et aversion des risques
Examine la théorie de l'utilité attendue, l'aversion pour les risques, les fonctions d'utilité et la prise de décisions sous l'incertitude.
Utilité attendue et Aversion au risque: fondements théoriques
Explore l'utilité attendue, l'aversion au risque, les primes d'assurance et le choix du portefeuille dans la tarification des actifs.
Méthodes informatiques: chemins et cordes
Couvre les méthodes de calcul se concentrant sur les chemins et les chaînes de caractères, y compris des exemples de concaténation, d'éléments régex et d'opérations de chaînes de caractères.
Afficher plus
Publications associées (17)

A PCP Theorem for Interactive Proofs and Applications

Alessandro Chiesa

The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multi ...
SPRINGER INTERNATIONAL PUBLISHING AG2022

Lower Bounds for Unambiguous Automata via Communication Complexity

Mika Tapani Göös, Weiqiang Yuan

We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. 1) Complement: There is a language L recognised by an n-state UFA such that the complement language ...
Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022

Enumeration of reversible functions and its application to circuit complexity

Giovanni De Micheli, Mathias Soeken, Nabila Abdessaied

We review combinational results to enumerate and classify reversible functions and investigate the application to circuit complexity. In particularly, we consider the effect of negating and permuting input and output variables and the effect of applying li ...
Springer2016
Afficher plus
Personnes associées (1)
Concepts associés (16)
Récursivement énumérable
En théorie de la calculabilité, un ensemble d'entiers naturels est récursivement énumérable ou semi-décidable si : il existe un algorithme qui prend un entier naturel en entrée, et qui s'arrête exactement sur les entiers de ; ou, de manière équivalente : il existe un procédé algorithmique qui, au cours de son fonctionnement, énumère en sortie tous les entiers de et seulement ceux-ci (il est possible, et même nécessaire quand est infini, qu'il ne s'arrête pas).
Théorie des automates
En informatique théorique, l'objectif de la théorie des automates est de proposer des modèles de mécanismes mathématiques qui formalisent les méthodes de calcul.
Computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines.
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.