Instituto Tecnológico de Jiquilpan

Teoría de la Computación

Unidad VI.- Reducibilidad

Jiquilpan, Michoacán a 01/Dic/10

Introducción

En el presente trabajo se expone un tema llamado redubilidad, veremos lo que es y se entenderá mejor con ejemplos, así como también veremos algunos temas desglosados de la reducibilidad obviamente con sus respectivas definiciones y aplicaciones.

Se pretende entender bien el tema de reducibilidad ya que es un tema básico que nos servirá para poder resolver o no problemas que se nos puedan atravesar en nuestra vida cotidiana diaria.

Redubibilidad

Por ejemplo suponiendo que quieres encontrar un camino para una nueva ciudad. Tú sabes que esto podría ser fácil si tú tuvieras un mapa. Así tú …ver más…

Tales funciones puede ser llamados A-computable o f-computable respectivamente. Antes la definición preciso de una función computable matemáticos solían usar el término informal efectivamente computable.
Funciones computables son usados para discutir computabilidad sin referir a ningún modelo de computación concreto, como máquina de Turing o máquina de registros. Los axiomas de Blum puede ser usados para definir una teoría de complejidad computacional abstracta sobre el conjunto de funciones computables.
Según el tesis Church-Turing, la clase de funciones computables es equivalente a la clase de funciones definidos por funciones recursivos, calculo de lamda, o algoritmos de Markov.
Alternativamente se pueden definir como los algoritmos que pueden ser calculados por máquina de Turing, sístema de Post, o máquina de registros.
En teoría de la complejidad computacional, el problema de determinar la complejidad de una función computable esta conocido como un problema de funciones.

Una función parcial está llamado computable si el gráfico de f es un conjunto recursivamente enumerable. El conjunto de funciones parcialmente computables con un parámetro es normalmente escrito o isi el número de parámetros es claro del contexto.
Una función total está llamado computable si el gráfico de f es un conjunto