Si queremos definir la Máquina de Turing en términos de función, podríamos decir que es: una función cuyo dominio se encuentra en la cinta infinita y es en esta misma donde se plasma su codominio, esto es, todos los posibles valores de entrada se encuentran en la cinta y todos …
Un algoritmo es un conjunto de pasos lógicos y secuenciales para solucionar un problema. Este concepto fue implementado en 1936 por Alan Turing, matemático inglés, en la llamada Máquina de Turing (MT). La Máquina de Turing está formada por tres elementos: una cinta, una cabeza de lectura-escritura y un programa. …
Se dice que un lenguaje es indecidible si sus miembros no pueden ser identificados por un algoritmo que restrinja todas las entradas en un número de pasos finito. Otra de sus propiedades es que no puede ser reconocido como una entrada válida en una máquina de Turing. Asociados a este …
Las gramáticas pueden ser de distintos tipos, de acuerdo con las características que rigen la formulación de reglas de producción válidas, todos los cuales parten de las gramáticas arbitrarias que son aquellas que consideran la existencia infinita de cadenas formadas por los símbolos del lenguaje. Los principales tipos derivados son: …
De lo anterior podemos decir que un lenguaje formal está constituido por un alfabeto, un vocabulario y un conjunto de reglas de producción definidas por gramáticas. Las frases válidas de un lenguaje formal son aquellas que se crean con los símbolos y palabras definidas tanto en el alfabeto como en …
