Ensayo decibilidad
Páginas: 2 (448 palabras)
Publicado: 1 de diciembre de 2010
ENSAYO EJECUTIVO DE DECIBILIDAD
Objetivo:
Dar a conocer a través de una breve definición que caracterizan y engloban al los conceptos de decibilidad, siendo este aplicado en la teoría deautómatas y lenguajes formales.
Desarrollo del Tema
¿Qué es la decibilidad?
Según definición un sistema lógico o teoría es decidible si el conjunto de todas las fórmulas válidas en el sistema esdecidible. Es decir, existe un algoricto tal que para cada fórmula del sistema es capaz de decidir en un número finito de pasos si la fórmula es válida o no en el sistema.
Ejemplo: La Lógica proposicional (sedefine una proposición como un enunciado declarativo que puede ser verdadero o falso, y Las proposiciones se representan mediante variables proposicionales simbolizadas mediante letras) es decidible,porque existe para ella un algoritmo; la tabla de verdad tal que para cada fórmula que combina M formulas atómicas, hay un número máximo N = 2M de pasos tal que tras completar estos N pasos elalgoritmo siempre decidirá si la fórmula es válida o no. Cada "paso" del algoritmo ha sido definido como una línea de la tabla de verdad.
La lógica de primer orden es decidible si se limita a predicadoscon un solo argumento. Si se incluyen predicados con dos o más argumentos, no es decidible.
Toda teoría completa recursivamente enumerable es decidible. Por otro lado, toda teoría que incluyaaritmética básica es no decidible.
En otras palabras se puede decir que un sistema formal es decidible si existe un algoritmo que diga en tiempo finito (quiere decir que deben estar establecidos cada unode los estados que lo forman, en otras palabras el tiempo debe estar señalado) si una cadena cualquiera es un teorema o no lo es.
Tambien hay que mencionar que en 1936, un matemático británico,Alan Turing, publica un ensayo titulado: “Acerca de Números Computables con una Aplicación al Problema de le Decidibilidad” (de Hilbert). En ese ensayo, introduce su máquina “pensante” primitiva,...
Objetivo:
Dar a conocer a través de una breve definición que caracterizan y engloban al los conceptos de decibilidad, siendo este aplicado en la teoría deautómatas y lenguajes formales.
Desarrollo del Tema
¿Qué es la decibilidad?
Según definición un sistema lógico o teoría es decidible si el conjunto de todas las fórmulas válidas en el sistema esdecidible. Es decir, existe un algoricto tal que para cada fórmula del sistema es capaz de decidir en un número finito de pasos si la fórmula es válida o no en el sistema.
Ejemplo: La Lógica proposicional (sedefine una proposición como un enunciado declarativo que puede ser verdadero o falso, y Las proposiciones se representan mediante variables proposicionales simbolizadas mediante letras) es decidible,porque existe para ella un algoritmo; la tabla de verdad tal que para cada fórmula que combina M formulas atómicas, hay un número máximo N = 2M de pasos tal que tras completar estos N pasos elalgoritmo siempre decidirá si la fórmula es válida o no. Cada "paso" del algoritmo ha sido definido como una línea de la tabla de verdad.
La lógica de primer orden es decidible si se limita a predicadoscon un solo argumento. Si se incluyen predicados con dos o más argumentos, no es decidible.
Toda teoría completa recursivamente enumerable es decidible. Por otro lado, toda teoría que incluyaaritmética básica es no decidible.
En otras palabras se puede decir que un sistema formal es decidible si existe un algoritmo que diga en tiempo finito (quiere decir que deben estar establecidos cada unode los estados que lo forman, en otras palabras el tiempo debe estar señalado) si una cadena cualquiera es un teorema o no lo es.
Tambien hay que mencionar que en 1936, un matemático británico,Alan Turing, publica un ensayo titulado: “Acerca de Números Computables con una Aplicación al Problema de le Decidibilidad” (de Hilbert). En ese ensayo, introduce su máquina “pensante” primitiva,...
Leer documento completo
Regístrate para leer el documento completo.