Proposición 4.3 (Tiempo compartido)
Para cada
![$m\geq 0$](img843.gif)
,
existe una máquina de Turing
![$\mbox{\it MTC}$](img844.gif)
tal que para cualesquiera
m máquinas de Turing
![$M_1,\ldots,M_m$](img835.gif)
y para cualquier entrada
![$\mbox{\bf x}$](img112.gif)
se tiene
Proposición 4.4 (Operando ``inter'' de máquinas)
Para cada
![$m\geq 0$](img843.gif)
,
existe una máquina de Turing
![$\mbox{\it MI}$](img846.gif)
tal que para cualesquiera
m máquinas de Turing
![$M_1,\ldots,M_m$](img835.gif)
y para cualquier entrada
![$\mbox{\bf x}$](img112.gif)
se tiene que
![$\mbox{\it MTC}(\mbox{\bf x})$](img847.gif)
asume el valor asumido por la máquina
Mi0 en
![$\mbox{\bf x}$](img112.gif)
,
si es que esa máquina es la primera, de entre todas las
Mi's, en detenerse al actuar sobre la entrada
![$\mbox{\bf x}$](img112.gif)
,
o bien queda indefinida,
![$\mbox{\it MTC}(\mbox{\bf x})=\perp$](img848.gif)
,
si todas las
Mi's lo quedan con
![$\mbox{\bf x}$](img112.gif)
.
La máquina
![$\mbox{\it MI}$](img846.gif)
se dice ser el
inter de las
Mi's y escribiremos
![$\mbox{\it MI}={\displaystyle\bigwedge_{i=1}^m M_i}$](img849.gif)
.