Teorema del isomorfismo de Myhill

En la teoría de la computabilidad, el teorema del isomorfismo de Myhill , que lleva el nombre de John Myhill , proporciona una caracterización de dos numeraciones para inducir la misma noción de computabilidad en un conjunto. Recuerda al teorema de Schröder-Bernstein en la teoría de conjuntos.

Teorema

Una reducción de muchos uno de un conjunto a un conjunto es una función computable total tal que . Una reducción uno uno es una reducción inyectiva y un isomorfismo computable es una reducción biyectiva. ${\displaystyle A\subseteq \mathbb {N} }$ ${\displaystyle B\subseteq \mathbb {N} }$ ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle \forall x\in \mathbb {N} ,x\in A\iff f(x)\in B}$

Teorema de isomorfismo de Myhill: Dos conjuntos son computablemente isomorfos si y sólo si A es uno-uno-reducible a B y B es uno-uno-reducible a A. ${\displaystyle A,B\subseteq \mathbb {N} }$

Como corolario, dos numeraciones totales son equivalentes a uno si y sólo si son recursivamente isomorfas .

Teorema de Myhill-Shepherdson

El teorema de Myhill-Shepherdson, ^[1] derivado del teorema de Rice-Shapiro , define los funcionales computables de tipo 2. Estos funcionales operan en funciones parciales computables, produciendo números como resultados en casos de terminación. En particular, se adhieren a un criterio de efectividad específico y exhiben continuidad como funcionales.

Considerando la noción de isomorfismo de Myhill, que establece que existe una biyección total computable, que mapea elementos reducibles entre sí en ambas direcciones, dado que las funciones son extensionales , ésta especifica la definición de funcionales recursivos .

En concreto, afirma:

1) Sea una función recursiva. Entonces, existe una función computable total tal que ${\displaystyle \phi :\mathbb {F} (\mathbb {N} ^{k})}$ ${\displaystyle \rightarrow \mathbb {F} (\mathbb {N} ^{i})}$ ${\displaystyle h_{\Phi }:\mathbb {N} \rightarrow \mathbb {N} }$ ${\displaystyle \forall e\in \mathbb {N} (\phi _{e}^{k})=\phi _{h_{(}\Phi )(e)}^{(i)}}$

2) Sea una función total computable y extensional. Entonces, existe un funcional recursivo único tal que ${\displaystyle h:\mathbb {N} \rightarrow \mathbb {N} }$ ${\displaystyle h}$ ${\displaystyle \phi :\mathbb {F} (\mathbb {N} ^{k})}$ ${\displaystyle \rightarrow \mathbb {F} (\mathbb {N} ^{i})}$ ${\displaystyle \forall e\in \mathbb {N} (\phi _{e}^{k})=\phi _{h(e)}^{(i)}}$

Discusión

El teorema implica que dadas dos reducciones inyectivas en direcciones opuestas, hay una biyección computable sobre los naturales que pone los conjuntos en cuestión en correspondencia biyectiva. Esto recuerda al teorema de Schröder-Bernstein sobre conjuntos generales, y al teorema de Myhill se le ha llamado una versión constructiva del mismo. ^[2] Sin embargo, sus pruebas son diferentes. La prueba de Schröder-Bernstein utiliza las inversas de las dos inyecciones, lo cual es imposible en el contexto del teorema de Myhill ya que estas inversas podrían no ser recursivas. La prueba del teorema de Myhill, por otro lado, define la biyección inductivamente, lo cual es imposible en el contexto de Schröder-Bernstein a menos que se utilice el axioma de elección (que no es necesario para la prueba del teorema de Myhill).

Ver también

• Conjetura de Berman-Hartmanis , una afirmación análoga en la teoría de la complejidad computacional .

Referencias

1. Dekker, JCE (septiembre de 1957). "J. Myhill y JC Shepherdson. Operaciones efectivas en funciones recursivas parciales. Zeitschrift für mathematische Logik und Grundlagen der Mathetnatik, vol. 1 (1955), págs. 310-317". La revista de lógica simbólica . 22 (3): 310–317. doi :10.2307/2963619. ISSN  0022-4812. JSTOR  2963619. S2CID  124280881.
2. P. Odifreddi, Teoría clásica de la recursión: la teoría de funciones y conjuntos de números naturales (p.320). Estudios de lógica y fundamentos de las matemáticas, vol. 125 (1989), Elsevier 0-444-87295-7.

• Myhill, John (1955), "Conjuntos creativos", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 1 (2): 97–108, doi :10.1002/malq.19550010205, SEÑOR  0071379.
• Rogers, Hartley Jr. (1987), Teoría de funciones recursivas y computabilidad efectiva (2ª ed.), Cambridge, MA: MIT Press, ISBN 0-262-68052-1, señor  0886890.
• Soare, Robert I. (1987), Conjuntos y grados recursivamente enumerables: un estudio de funciones computables y conjuntos generados computablemente, Perspectives in Mathematical Logic, Berlín Heidelberg: Springer-Verlag, ISBN 978-3-540-66681-3, MR 0882921