Llenguatge enumerable recursivament

En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge enumerable recursivament (o també parcialment decidible o Turing-computable) si és un subconjunt enumerable recursivament del conjunt de totes les paraules amb l'alfabet del llenguatge. Equivalentment, un llenguatge és enumerable recursivament si existeix una màquina de Turing que accepta i s'atura amb qualsevol cadena del llenguatge.[1][2][3]

Aquest tipus de llenguatges s'etiqueten com de tipus 0 en la jerarquia de Chomsky dels llenguatges formals. Tots els llenguatges regulars, lliures de context i recursius son llenguatges enumerables recursivament.

La classe de tots els llenguatges enumerables recursivament s'anomena RE.

DefinicionsModifica

Hi ha tres definicions equivalents d'un llenguatge enumerable recursivament:

  1. Un llenguatge enumerable recursivament és un subconjunt enumerable recursivament del conjunt de totes les possibles paraules de l'alfabet del llenguatge.
  2. Un llenguatge enumerable recursivament és un llenguatge formal pel que existeix una màquina de Turing (o alguna altra funció computable) que enumerarà totes les cadenes vàlides del llenguatge.
  3. Un llenguatge enumerable recursivament és un llenguatge formal pel que existeix una màquina de Turing ( o alguna altra funció computable) que s'aturarà i acceptarà quan se li presenti qualsevol cadena del llenguatge com a entrada, però que o bé s'aturarà i rebutjarà o no s'aturarà mai quan la cadena no sigui del llenguatge. Això diferència aquest tipus de llenguatge dels llenguatges recursius, on la màquina ha d'aturar-se en tots els casos.

Tots els llenguatges regulars, lliures de context i recursius son llenguatges enumerables recursivament.

El teorema de Post demostra que la classe RE juntament amb la seva complementaria co-RE es corresponent al primer nivell de la jerarquia aritmètica.

Propietats de clausuraModifica

Els llenguatges enumerables recursivament son tancats segons les següents operacions. Si L i P son dos llenguatges enumerables recursivament, llavors els següents llenguatges també ho son:

Els llenguatges enumerables recursivament no estan tancats respecte a la diferència de conjunts o complementari. El conjunt diferència L - P pot ser o pot no ser enumerable recursivament. Si L és enumerable recursivament, llavors el complement d'L és enumerable recursivament si i només si L és també recursiu.

Vegeu TambéModifica

ReferènciesModifica

  1. «Complexity Zoo:R - Complexity Zoo» (en anglès). [Consulta: 28 novembre 2018].
  2. Michael., Sipser,. Introduction to the theory of computation. 2nd ed. Boston: Thomson Course Technology, 2006. ISBN 0534950973. 
  3. 1951-, Kozen, Dexter,. Automata and computability. Nova York: Springer, 1997. ISBN 0387949070.