Llenguatge enumerable recursivament: diferència entre les revisions

Robot estandarditza i catalanitza referències, catalanitza dates i fa altres canvis menors
(nova creació)
 
(Robot estandarditza i catalanitza referències, catalanitza dates i fa altres canvis menors)
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.<ref>{{Ref-web|url=https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#re|títol=Complexity Zoo:R - Complexity Zoo|consulta=2018-11-28|llengua=en}}</ref><ref>{{Ref-llibre|cognom=Michael.|nom=Sipser,|títol=Introduction to the theory of computation|url=https://www.worldcat.org/oclc/58544333|edició=2nd ed|data=2006|editorial=Thomson Course Technology|lloc=Boston|isbn=0534950973}}</ref><ref>{{Ref-llibre|cognom=1951-|nom=Kozen, Dexter,|títol=Automata and computability|url=https://www.worldcat.org/oclc/35911836|data=1997|editorial=Springer|lloc=NewNova York|isbn=0387949070}}</ref>
 
Aquest tipus de llenguatges s'etiqueten com de tipus 0 en la [[jerarquia de Chomsky]] dels llenguatges formals. Tots els llenguatges [[Llenguatge regular|regulars]], [[Llenguatge lliure de context|lliures de context]] i [[Llenguatge recursiu|recursius]] son llenguatges enumerables recursivament.
575.022

modificacions