¿Cuál es la relación entre la capacidad de decisión de un predicado y la capacidad de cálculo de una función?

Answer 1

Un predicado [matemática] P [/ matemática] es decidible si hay algún medio efectivo para determinar, para cada [matemática] x [/ matemática] en el universo, si [matemática] P (x) [/ matemática] o [matemática ] \ neg P (x) [/ math] se mantiene. El universo en este caso se refiere a [math] \ mathbb {N}, [/ math] el conjunto de números naturales.

Aquí “medios efectivos” podría referirse a la existencia de una máquina de Turing, o una función recursiva [matemática] \ mu – [/ matemática], o algo más, dependiendo de su modelo de cómputo. La tesis de Church-Turing dice que todos los modelos de computación son esencialmente intercambiables.

Para cualquier predicado [matemático] P [/ matemático], puede definir una función indicadora asociada [matemática] f_P: U \ rightarrow \ {0,1 \}. [/ Matemático] El dominio de esta función es el universo, y rango es el conjunto [matemática] \ {0,1 \}. [/ matemática] Los valores de [matemática] f [/ matemática] están determinados por

[matemáticas] f_P (x) = 1 \ iff \ modelos P (x) [/ matemáticas]

[matemáticas] f_P (x) = 0 \ iff \ modelos \ neg P (x) [/ matemáticas]

Tenga en cuenta que la función [math] f_P [/ math] y el predicado [math] P [/ math] están determinados esencialmente por la misma información, es decir, el subconjunto del universo que satisface [math] P. [/matemáticas]

Si tiene una noción de una función computable – Wikipedia, entonces puede definir [math] P [/ math] para que sea computable iff [math] f_P [/ math] es una función computable que se define para cada [math] x \ in U. [/ math] Conjunto recursivo – Wikipedia