Sé un poco sobre lo que es un turing-machine y un idioma, pero para entender mejor, ¿alguien podría dar ejemplos de idiomas que no están completos? (tal vez incluso las máquinas que no son Turing, también?)Buscando idiomas que no están completos Turing
Las expresiones regulares, en la definición formal, que consiste solamente en:
solo se pueden reconocer idiomas regulares. Un lenguaje de programación completo de Turing puede reconocer lenguajes enumerables recursivamente.
Un ejemplo es que las expresiones regulares no pueden decirle si una cadena consta de pares de paréntesis coincidentes: por ejemplo, se acepta ()(()) mientras ()((())(), mientras que los lenguajes de programación de Turing pueden completar.
(Tenga en cuenta que las expresiones regulares en lenguajes de programación modernos son más poderosos que la definición académica formal de expresiones regulares. Algunos pueden incluso ser Turing completo.)
Regular languages - los que se pueden describir como expresiones regulares - son not Turing complete.
Los lenguajes de marcado (utilizados para describir datos, no el cálculo) como XML y JSON no están completos.
La diferencia entre los datos y el cálculo es complicado. [LaTeX] (http://stackoverflow.com/questions/2968411/ive-heard-that-latex-is-turing-complete-are-herehere-any-programs-written-in-latex) es Turing-completo, a pesar de siendo un lenguaje de procesamiento de texto. –
@Phillip: No del todo justo, ya que LaTeX tiene acceso a todos los TeX que se pretende (al menos en parte) para ser un lenguaje de uso general. Consulte la página de Knuth, donde responde la pregunta "¿Cuál es su idioma favorito?". – Charles
Por ejemplo, la expresión regular de Perl puede ser recursiva: http://www.catonmat.net/blog/recursive-regular-expressions PHP regexp tiene el indicador/e para evaluar las expresiones de PHP en la sustitución. –
@SHi: gracias por eso, ¡muy interesante! –
Una vez vimos una expresión regular en Perl que hacía coincidir cadenas con una longitud que era solo un número primo. Usé el back-track y tardé bastante ... –