DSN_XP y el modelo Kruchten

Planos arquitectónicos: 
la vista "4 + 1"
Modelo de arquitectura de software

Philippe Kruchten Rational Software Corp
Artículo publicado en IEEE Software 12 (6)

Noviembre de 1995, págs. 42-50

Resumen

Este artículo presenta un modelo para describir la arquitectura de sistemas intensivos en software, basado en el uso de múltiples vistas concurrentes. Este uso de múltiples vistas permite abordar por separado las preocupaciones de varias 'partes interesadas' de la arquitectura: usuario final, desarrolladores, ingenieros de sistemas, directores de proyectos, etc., y manejar por separado los requisitos funcionales y no funcionales

Se describe cada una de las cinco vistas, junto con una notación para capturarlo. Las vistas se diseñan utilizando un escenario centrado en la arquitectura, guiando el proceso de desarrollo iterativo

Palabras clave : arquitectura de software, vista, diseño orientado a objetos, proceso de desarrollo de software

Introducción 

Todos hemos visto muchos libros y artículos en los que un diagrama intenta capturar la esencia de la arquitectura de un sistema. Pero al observar cuidadosamente el conjunto de cuadros y flechas que se muestran en estos diagramas, queda claro que sus autores han luchado mucho para representar en un plano más de lo que realmente puede expresar
  • ¿Son las casillas que representan los programas en ejecución? 
  • ¿O trozos de código fuente? 
  • ¿O computadoras físicas? 
  • ¿O simplemente agrupaciones lógicas de funcionalidad? 
  • ¿Las flechas representan dependencias de compilación? 
  • ¿O controlar flujos? 
  • ¿O flujos de datos? 
Suele ser un poco de todo. ¿Necesita una arquitectura única? ¿un estilo arquitectónico único? A veces, la arquitectura del software sufre cicatrices debido a un diseño de sistema que fue demasiado prematuramente particionado el software, o por un énfasis excesivo en un aspecto del desarrollo de software: ingeniería de datos, o por la eficiencia en tiempo de ejecución, o estrategia de desarrollo y organización de equipos

A menudo también la arquitectura no aborda las preocupaciones de todos sus "clientes" (o "partes interesadas", como se les llama en USC). Este problema ha sido notado por varios autores: Garlan & Shaw 1 , Abowd & Allen en CMU,  Clements en el SEI. 
Como remedio, proponemos organizar la descripción de una arquitectura de software utilizando varias opiniones concurrentes, cada una de las cuales aborda un conjunto específico de preocupaciones.

Un modelo arquitectónico

La arquitectura del software se ocupa del diseño y la implementación de la estructura de alto nivel del software. Eso es el resultado de ensamblar un cierto número de elementos arquitectónicos en algunas formas bien elegidas para satisfacer los principales requisitos de funcionalidad y rendimiento del sistema, así como algunos otros requisitos no funcionales, requisitos como confiabilidad, escalabilidad, portabilidad y disponibilidad

Perry y Wolfe lo expresaron muy bien en esta fórmula2, modificada por Boehm

Arquitectura de software = {Elementos, formas, fundamento / restricciones} 
La arquitectura de software se ocupa de la abstracción, la descomposición y la composición, el estilo y la estética
Para describir una arquitectura de software, utilizamos un modelo compuesto por múltiples vistas o perspectivas. A fin de que eventualmente abordar arquitecturas grandes y desafiantes, el modelo que proponemos se compone de cinco vistas principales(ver figura 1):

  • La vista lógica, la cual es el modelo de objetos del diseño (cuando se utiliza el método de diseño orientado a objetos), 
  • La vista del proceso, que captura los aspectos de simultaneidad y sincronización del diseño,
  • La vista física, que describe el mapeo(s) del software en el hardware y refleja su aspecto distribuido,
  • La vista de desarrollo, que describe la organización estática del software en su ambiente de desarrollo.
La descripción de una arquitectura (las decisiones tomadas) se pueden organizar en torno a estas cuatro vistas y luego se ilustra con algunos casos de uso seleccionados o escenarios que se convierten en una quinta vista. 

La arquitectura de hecho evolucionó parcialmente a partir de estos escenarios como veremos más adelante.

Aplicamos la ecuación de Perry & Wolf independientemente en cada vista, es decir, para cada vista definimos el conjunto de elementos a utilizar (componentes, contenedores y conectores), capturamos las formas y patrones que funcionan y capturamos el fundamento y las limitaciones, conectando la arquitectura con algunos de los requisitos. 
Cada vista se describe mediante un plano que utiliza su propia notación particular. Para cada vista también, los arquitectos puede elegir un determinado estilo arquitectónico, lo que permite la coexistencia de múltiples estilos en un sistema. 
Ahora veremos sucesivamente cada uno de los cinco puntos de vista, dando para cada uno su propósito: lo que se refiere a las direcciones, una notación para el plano arquitectónico correspondiente, las herramientas que hemos utilizado para describirlo y administrarlo. 

Se extraen pequeños ejemplos del diseño de una centralita, derivado de nuestro trabajo en Alcatel Business System y un sistema de control de tráfico aéreo 3, pero en una forma muy simplificada, la intención aquí es solo dar una idea de las vistas y su notación y no definir la arquitectura de esos sistemas. 

El modelo de vista "4 + 1" es bastante "genérico": se pueden usar otras notaciones y herramientas, otros especialmente métodos de diseño para las descomposiciones lógicas y de proceso, pero hemos indicado las que han sido utilizadas con éxito.

La arquitectura lógica 

La descomposición orientada a objetos 

La arquitectura lógica soporta principalmente los requisitos funcionales: lo que el sistema debe proporcionar en condiciones de servicio a sus usuarios. El sistema se descompone en un conjunto de abstracciones clave, tomadas (en su mayoría) del dominio del problema, en forma de objetos o clases de objetos

Aprovechamos los principios de la abstracción, encapsulación y herencia. Esta descomposición no es solo por el análisis funcional, sino que también sirve para identificar mecanismos comunes y elementos de diseño en las distintas partes del sistema. 

Usamos el enfoque Rational / Booch para representar la arquitectura lógica, mediante diagramas de clases y plantillas de clases.4  Un diagrama de clases muestra un conjunto de clases y sus relaciones lógicas: asociación, uso, composición, herencia, etc. Los conjuntos de clases relacionadas se pueden agrupar en categorías de clases. Las plantillas de clase se centran en cada clase individual; enfatizan las operaciones de la clase principal e identifican el objeto y sus características clave. 

Si es importante definir el comportamiento interno de un objeto, esto se hace con diagramas de transición de estado. o diagramas de estado. Los mecanismos o servicios comunes se definen en las clases de utilidades. 

Alternativamente a un enfoque orientado a objetos, una aplicación que está basada mucho en los datos puede usar alguna otra forma de vista lógica, como diagramas ER. 

Notación para la vista lógica 

La notación para la vista lógica se deriva de la notación de Booch4 . Esta es considerablemente simplificada y toma en cuenta solo los elementos que son arquitectónicamente significativos. En particular, los numerosos adornos no son muy útiles en este nivel de diseño. Usamos Rational Rose® para respaldar el diseño de la arquitectura lógica. 

Estilo para la vista lógica 

El estilo que usamos para la vista lógica es un estilo orientado a objetos. La principal directriz para el diseño de la vista lógica es tratar de mantener un modelo de objetos único y coherente en todo el sistema, para evitar la especialización de clases y mecanismos por sitio o por procesador.

Ejemplos de planos lógicos 

La Figura 3a muestra las principales clases involucradas en la arquitectura de Télic PABX


Un PABX establecen comunicaciones entre terminales. Una terminal puede ser un teléfono, una línea troncal (es decir, línea a la oficina central), una línea de enlace (es decir, línea PABX privada a PABX), una línea telefónica de función, una línea de datos, un línea ISDN, etc. 

Las diferentes líneas son soportadas por tarjetas de interfaz de líneas.  La responsabilidad de un objeto controlador de línea es decodificar e inyectar todas las señales hacia la tarjeta de interfaz de línea, traduciendo hacia y desde un conjunto pequeño y uniforme de eventos: inicio, parada, dígito, etc. El controlador también lleva todos las estricciones estrictas en tiempo real. Esta clase tiene muchas subclases para adaptarse a diferentes tipos de interfaces. 

La responsabilidad del objeto terminal es mantener el estado de una terminal y negociar servicios en nombre de esa línea. Por ejemplo, utiliza los servicios del plan de numeración para interpretar la marcación en la fase de selección. 

La conversación representa un conjunto de terminales involucrados en la conversación. La conversación usa servicios de traducción (directorio, asignación de direcciones lógicas a físicas, rutas) y servicios de conexión al establecer una ruta de voz entre los terminales. 

Para sistemas mucho más grandes, que contienen congeladas unas pocas docenas de clases de importancia arquitectónica, la figura 3b muestra el diagrama de clase de nivel superior de un sistema de control de tránsito aéreo, que contiene 8 categorías de clase (es decir, grupos de clases). 

La Arquitectura de Procesos

El proceso de descomposición 

La arquitectura de procesos tiene en cuenta algunos requisitos no funcionales, como el rendimiento y la
disponibilidad. Aborda problemas de concurrencia y distribución, de la integridad del sistema, de la tolerancia a fallas y cómo las principales abstracciones de la vista lógica encajan dentro de la arquitectura de procesos, en qué hilo del control realmente se está ejecutado una operación para un objeto. 

La arquitectura de procesos se puede describir en varios niveles de abstracción, cada nivel aborda diferentes preocupaciones. En el nivel más alto, la arquitectura de procesos se puede ver como un conjunto de "procesos" en ejecución independiente como redes lógicas de programas de comunicación (llamados "procesos"), distribuidos en un conjunto de recursos hardware conectados por una LAN o una WAN. 

Pueden existir múltiples redes lógicas simultáneamente, compartiendo los mismos recursos físicos. Por ejemplo, se pueden utilizar redes lógicas independientes para soportar la separación del sistema operativo en línea desde el sistema fuera de línea, así como el apoyo a la coexistencia de la simulación o probar versiones del software.

Un proceso es una agrupación de tareas que forman una unidad ejecutable. Los procesos representan el nivel en el que la arquitectura de procesos se puede controlar tácticamente (es decir, iniciar, recuperar, reconfigurar y apagar). Además, los procesos se pueden replicar para una mayor distribución de la carga de procesamiento, o para mejorar disponibilidad. 

El software es dividido en un conjunto de tareas independientes . Una tarea es un hilo de control separado, que puede ser programados individualmente en un nodo de procesamiento. 

Podemos distinguir entonces: las tareas principales , que son los elementos arquitectónicos que pueden ser abordados y tareas menores, que son tareas adicionales introducidas localmente por razones de implementación (actividades cíclicas, búfer, tiempos muertos, etc.). Se pueden implementar como tareas de Ada por ejemplo, o como hilos ligeros.

Las tareas principales se comunican a través de un conjunto de mecanismos de comunicación entre tareas bien definidos: síncronos y servicios de comunicación asíncronos basados ​​en mensajes, llamadas a procedimientos remotos, difusión de eventos, etc. Las tareas pueden comunicarse por encuentro o memoria compartida. Las tareas principales no deben hacer suposiciones sobre su colocación en el mismo proceso o nodo de procesamiento

El flujo de mensajes, las cargas de procesos se pueden estimar en función plantillas de procesos. También es posible implementar una arquitectura de proceso "hueca" con cargas ficticias para los procesos y medir su rendimiento en el sistema objetivo, como lo describen Filarey et al. en su experimento de Eurocontrol. 

Notación para la vista de Procesos

La notación que usamos para la vista de procesos, amplía la notación propuesta originalmente por Booch para Tareas Ada. Una vez más, la notación utilizada se centra en los elementos que son arquitectónicamente significativos. (Figura 4)


Hemos utilizado el producto Universal Network Architecture Services (UNAS) de TRW para diseñar e implementar el conjunto de procesos y tareas (y sus redundancias) en redes de procesos. UNAS contiene una herramienta, el entorno del ciclo de vida de software de arquitectos  (SALE), que admite dicha notación. 

SALE permite la representación gráfica de la arquitectura del proceso, incluidas las especificaciones de los posibles rutas de comunicación entre tareas, de las que se extrae automáticamente el código fuente Ada o C ++ automáticamente generado. El beneficio de este enfoque para especificar e implementar la arquitectura del proceso es que los cambios se pueden incorporar fácilmente sin mucho impacto en el software de la aplicación

Estilo para la vista de procesos

Varios estilos encajarían en la vista del procesos. Por ejemplo, tomando de la taxonomía1 de Garlan y Shaw podemos tener: canalizaciones y filtros, o cliente / servidor, con variantes de cliente / servidor único y múltiples clientes / servidores múltiples. Para sistemas más complejos, se podría usar un estilo similar a los grupos de procesos enfoque del sistema ISIS como lo describe K. Birman con otra notación y conjunto de herramientas.

Ejemplo de una plantilla de procesos


Todos las terminales son manejadas por un solo proceso de terminal, que es impulsado por mensajes en sus colas de entrada. Los objetos del controlador se ejecutan en una de las tres tareas que componen el proceso del controlador: Una tarea de ciclo de frecuencia baja escanea todos los terminales inactivos (200 ms), coloca cualquier terminal que llegue a activarse en la lista de escaneo del alto tarea de frecuencia de ciclo (10 ms), que detecta cualquier cambio de estado significativo y los pasa a las tareas del controlador principal que interpreta los cambios y los comunica por mensaje al terminal correspondiente. Aquí el paso de mensajes dentro del proceso del controlador se realiza a través de la memoria compartida.

La arquitectura de desarrollo

Descomposición del subsistema

La arquitectura de desarrollo se centra en la real organización de módulos de software en el entorno de desarrollo de software. El software está empaquetado en pequeños fragmentos (bibliotecas de programas o subsistemas ) que pueden ser desarrollados por uno o un pequeño número de desarrolladores. Los subsistemas están organizados en una jerarquía de capas, cada capa proporciona una interfaz estrecha y bien definida con las capas superiores.

La arquitectura de desarrollo del sistema está representada por diagramas de módulos y subsistemas, que muestran la relaciones de 'exportación' e 'importación'. La arquitectura de desarrollo completa solo se puede describir cuando se han identificado todos los elementos del software. Sin embargo, es posible enumerar las reglas que gobiernan la arquitectura de desarrollo: particionamiento, agrupamiento, visibilidad.

En su mayor parte, la arquitectura de desarrollo tiene en cuenta los requisitos internos relacionados con la facilidad de desarrollo, gestión de software, reutilización o comunidad y a las limitaciones impuestas por el conjunto de herramientas, o el lenguaje de programación. La vista de desarrollo sirve como base para la asignación de requisitos, para asignación de trabajo a equipos (o incluso para la organización de equipos), para la evaluación y planificación de costos, para monitorear el avance del proyecto, para razonar sobre reutilización, portabilidad y seguridad del software. Es la base para establecer una línea de producto.

Notación para la plantilla de desarrollo

Nuevamente, una variación de la notación de Booch, limitándola a los elementos que son arquitectónicamente significativos. 


El entorno de desarrollo de Apex de Rational apoya la definición y la implementación de la arquitectura de desarrollo, la estrategia de capas descrita anteriormente y la aplicación de las reglas de diseño.

Rational Rose puede dibujar las plantillas de desarrollo a nivel de módulo y subsistema, en adelante ingeniería y por ingeniería inversa del código fuente de desarrollo, para Ada y C ++.

Estilo para la vista de desarrollo

Recomendamos adoptar un estilo en capas para la vista de desarrollo, definiendo entre 4 y 6 capas de subsistemas. Cada capa tiene una responsabilidad bien definida. La regla de diseño es que un subsistema en una determinada capa solo depende de subsistemas que se encuentran en la misma capa o en capas inferiores, para minimizar la desarrollo de redes muy complejas de dependencias entre módulos y permitir estrategias de liberación sencillas, capa por capa.

Ejemplo de arquitectura de desarrollo

La Figura 6 representa la organización de desarrollo en cinco capas de una línea de producto de control de tráfico aéreo, sistemas desarrollados por Hughes Aircraft of Canada3 . Esta es la arquitectura de desarrollo correspondiente a la  lógica mostrada en la fig. 3b.

Las capas 1 y 2 constituyen una infraestructura distribuida independiente del dominio que es común en la línea de productos y lo protege de variaciones en la plataforma de hardware, el sistema operativo o los productos disponibles en el mercado como el sistema de gestión de bases de datos. A esta infraestructura, la capa 3 agrega un marco ATC para formar una arquitectura de software de dominio específico . Con este marco, se crea una paleta de funciones en la capa 4.

La capa 5 depende en gran medida del cliente y del producto y contiene la mayor parte de la interfaz de usuario y las interfaces con los sistemas externos. Unos 72 subsistemas se distribuyen en las 5 capas, que contienen cada una de 10 av50 módulos y se pueden representar en planos adicionales.

La Arquitectura Física

Mapeo del software al hardware

La arquitectura física tiene en cuenta principalmente los requisitos no funcionales del sistema, como la disponibilidad, la confiabilidad (tolerancia a fallas), el rendimiento (rendimiento) y la escalabilidad. El software se ejecuta en una red de computadoras o nodos de procesamiento (o simplemente nodos para abreviar). Los diversos elementos identificados: redes, procesos, tareas y objetos: deben asignarse a los distintos nodos. Esperamos que se utilizarán varias diferentes configuraciones físicas: algunas para el desarrollo y las pruebas, otras para la implementación del sistema para varios sitios o para diferentes clientes. El mapeo del software a los nodos por lo tanto, debe ser muy flexible y tener un impacto mínimo en el código fuente en sí.

Notación para el plano físico

Los planos físicos pueden volverse muy confusos en sistemas grandes, por lo que toman varias formas, con o sin el mapeo desde la vista del proceso.


UNAS de TRW nos proporciona aquí medios basados ​​en datos para mapear la arquitectura del proceso en la arquitectura física que permite una gran clase de cambios en el mapeo sin modificaciones en el código fuente.

Ejemplo de una plantilla física



La figura 8 muestra una posible configuración de hardware para una centralita telefónica grande, mientras que las figuras 9 y 10 muestran mapeos de la arquitectura del proceso en dos arquitecturas físicas diferentes, correspondientes a una pequeña y una PABX grande. C, F y K son tres tipos de computadoras de diferente capacidad, que admiten tres diferentes ejecutables


Escenarios

Poniéndolo todo junto

Se muestra que los elementos de las cuatro vistas funcionan juntos a la perfección mediante el uso de un pequeño conjunto de elementos importantes, los escenarios —instancias de casos de uso más generales— para los cuales describimos los scripts correspondientes (secuencias de interacciones entre objetos y entre procesos) como lo describen Rubin y Goldberg6. Los escenarios son en cierto sentido una abstracción de los requisitos más importantes. Su diseño es expresado utilizando diagramas de escenarios de objetos y diagramas de interacción de objetos4.

Esta vista es redundante con las otras (de ahí el "+1"), pero tiene dos propósitos principales:
  • como impulsor para descubrir los elementos arquitectónicos durante el diseño de la arquitectura como describiremos más adelante,
  • como una función de validación e ilustración después de que este diseño de arquitectura esté completo, tanto en papel como punto de partida para las pruebas de un prototipo arquitectónico.

Notación para los escenarios

La notación es muy similar a la vista lógica para los componentes (ver fig.2), pero usa los conectores de la vista de procesos para interacciones entre objetos (ver fig. 4). Tenga en cuenta que las instancias de objetos se indican con líneas solidas. En cuanto al plano lógico, capturamos y gestionamos diagramas de escenarios de objetos utilizando Rational Rose.

Ejemplo de un escenario

La Fig. 11 muestra un fragmento de un escenario para la PABX pequeña. El script correspondiente dice:
  1. El controlador del teléfono de Joe detecta y valida la transición de colgado a descolgado y envía un mensaje para despertar el objeto terminal correspondiente.
  2. El terminal asigna algunos recursos y le dice al controlador que emita algún tono de marcación.
  3. El controlador recibe dígitos y los transmite al terminal.
  4. El terminal utiliza el plan de numeración para analizar el flujo de dígitos.
  5. Cuando se ingresa una secuencia válida de dígitos, el terminal abre una conversación.

Correspondencia entre las vistas

Las distintas vistas no son totalmente ortogonales ni independientes. Los elementos de una vista están conectados a elementos en otras vistas, siguiendo ciertas reglas de diseño y heurísticas.

De la visión lógica a la de procesos

Identificamos varias características importantes de las clases de la arquitectura lógica: 
  • Autonomía: ¿los objetos son activos, pasivos, protegidos?
  1. un objeto activo toma la iniciativa de invocar las operaciones de otros objetos o sus propias operaciones y tiene control total sobre la invocación de sus propias operaciones por otros objetos
  2. un objeto pasivo nunca invoca espontáneamente ninguna operación y no tiene control sobre la invocación de sus propias operaciones por otros objetos
  3. un objeto protegido nunca invoca espontáneamente ninguna operación, pero realiza algún arbitraje sobre la invocación de sus operaciones.
  • Persistencia: ¿los objetos son transitorios, permanentes? ¿Son la falla de un proceso o procesador?
  • Subordinación: ¿la existencia o persistencia de un objeto depende de otro objeto? 
  • Distribución: son el estado o las operaciones de un objeto accesible desde muchos nodos en la arquitectura física, desde varios procesos en la arquitectura de procesos? 
En la vista lógica de la arquitectura, consideramos cada objeto como activo y potencialmente "concurrente", es decir, comportarse "en paralelo" con otros objetos y no prestamos más atención al grado exacto de concurrencia, necesitamos lograr este efecto. Por tanto, la arquitectura lógica sólo tiene en cuenta el aspecto funcional de los requisitos. 

Sin embargo, cuando llegamos a definir la arquitectura del proceso, implementar cada objeto con su propio hilo de control (por ejemplo, su propio proceso Unix o tarea Ada) no es muy práctico en el estado actual de la tecnología, debido a la enorme sobrecarga que esto impone. Además, si los objetos son concurrentes, debe haber alguna forma de arbitraje para invocar sus operaciones. 

Por otro lado, se necesitan múltiples hilos de control por varias razones:
  • Reaccionar rápidamente a ciertas clases de estímulos externos, incluidos eventos relacionados con el tiempo.
  • Para aprovechar varias CPU en un nodo o varios nodos en un sistema distribuido
  • Para aumentar la utilización de la CPU, asignando la CPU a otras actividades mientras se controla algo está suspendido esperando a que se complete alguna otra actividad (por ejemplo, acceso a algún dispositivo externo o acceso a algún otro objeto activo) 
  • Para priorizar actividades (y potencialmente mejorar la capacidad de respuesta) 
  • Para respaldar la escalabilidad del sistema (con procesos adicionales que comparten la carga)
  • Separar preocupaciones entre diferentes áreas del software. 
  • Para lograr una mayor disponibilidad del sistema (con procesos de respaldo) 
Usamos simultáneamente dos estrategias para determinar la cantidad 'correcta' de concurrencia y definir el conjunto de procesos que se necesitan. Teniendo en cuenta el conjunto de posibles arquitecturas de destino físico, podemos continuar ya sea: 
  • De adentro hacia afuera:
    Partiendo de la arquitectura lógica: defina las tareas del agente que multiplexen un solo hilo de control a través de múltiples objetos activos de una clase; objetos cuya persistencia o vida está subordinada a un objeto activo también se ejecuta en ese mismo agente; varias clases que deben ejecutarse en mutua exclusión, o que requieren solo una pequeña cantidad de procesamiento comparten un solo agente. Este agrupamiento continúa hasta que hayamos reducido los procesos a un número razonablemente pequeño que aún permite la distribución y uso de los recursos físicos.
  • De fuera hacia dentro:
    Empezando por la arquitectura física: identificar estímulos externos (peticiones) al sistema, definir procesos cliente para manejar los estímulos y procesos servidores que solo brindan servicios y no inician ellos; utilizar la integridad de los datos y las restricciones de serialización del problema para definir el conjunto correcto de servidores y asignar objetos a los agentes del cliente y servidores; identificar qué objetos deben distribuirse.
El resultado es un mapeo de clases (y sus objetos) en un conjunto de tareas y procesos del proceso arquitectura. Normalmente, hay una tarea de agente para una clase activa, con algunas variaciones: varios agentes para una clase dada para aumentar el rendimiento, o varias clases asignadas a un solo agente porque sus operaciones se invocan con poca frecuencia o para garantizar la ejecución secuencial.

Tenga en cuenta que este no es un proceso determinista lineal que conduce a una arquitectura de proceso óptima; se requiere unas pocas iteraciones para conseguir un compromiso aceptable . Hay muchas otras formas de proceder, como se muestra en Birman y col. 5 o Witt et al. 7 por ejemplo. El método preciso utilizado para construir el mapeo está fuera del alcance de este artículo, pero podemos ilustrarlo con un pequeño ejemplo.

La figura 12 muestra cómo se puede mapear un pequeño conjunto de clases de algún sistema hipotético de control de tráfico aéreo en procesos.

La clase de vuelo se asigna a un conjunto de agentes de vuelo, hay muchos vuelos para procesar, una alta tasa de estímulos externos, el tiempo de respuesta es crítico, la carga debe distribuirse entre varias CPU. Además los aspectos de persistencia y distribución del procesamiento del vuelo se difieren a un servidor de vuelo, que es duplicado por razones de disponibilidad.

Un perfil de vuelo o una autorización están siempre subordinados a un vuelo y aunque existen clases complejas, comparten los procesos de la clase de vuelo. Los vuelos se distribuyen a varios otros procesos, en particular para pantalla e interfaces externas.

Una clase de sectorización, que estableció una partición del espacio aéreo para la asignación de jurisdicción de los controladores sobre vuelos, debido a sus limitaciones de integridad, pueden ser manejados por un solo agente, pero pueden compartir el proceso del servidor con el vuelo: las actualizaciones son poco frecuentes.

Ubicaciones y el espacio aéreo y otra información estática aeronáutica están protegidos objetos, compartida entre varias clases, rara vez actualizadas; se mapean en su propio servidor y se distribuyen a otros procesos.

De la lógica al desarrollo

Una clase generalmente se implementa como un módulo, por ejemplo, un tipo en la parte visible de un paquete Ada. Clases grandes se descomponen en varios paquetes. Las colecciones de clases estrechamente relacionadas (categorías de clases) se agrupan en subsistemas. Se deben considerar restricciones adicionales para la definición de subsistemas, como la organización del equipo, la magnitud esperada del código (típicamente 5K a 20K SLOC por subsistema), grado de reutilización esperada y elementos comunes y principios estrictos de estratificación por capas (problemas de visibilidad), política de liberación y gestión de la configuración. Por lo tanto, solemos terminar con una vista que no tiene una  correspondencia uno a uno con la visión lógica.

Las vistas lógica y de desarrollo son muy cercanas, pero abordan preocupaciones muy diferentes. Hemos encontrado que cuanto mayor sea el proyecto, mayor será la distancia entre estas vistas. Del mismo modo entre la vista de procesos y la vista física de despliegue.

Por ejemplo, si comparamos la fig. 3b y fig. 6, no hay un mapeo de uno a uno de las categorías de clase a las capas. Si tomamos las interfaces externas: categoría puerta de enlace, su implementación se distribuye en varias capas: los protocolos de comunicaciones están en subsistemas en o debajo de la capa 1, los mecanismos de puerta de enlace generales están en subsistemas en la capa 2, y las pasarelas específicas reales en subsistemas de capa 5.

Del proceso al físico de despliegue

Los procesos y los grupos de procesos se asignan al hardware físico disponible, en varias configuraciones para pruebas o implementación. Birman describe algunos esquemas muy elaborados para este mapeo en el proyecto Isis5 .

Los escenarios se relacionan principalmente con la vista lógica, en términos de las clases que se utilizan, y con la vista del proceso, cuando las interacciones entre objetos involucran más de un hilo de control.

Adaptación del modelo

No toda arquitectura de software necesita las vistas completas “4 + 1”.  Las vistas que son inútiles se pueden omitir de la descripción de la arquitectura, como la vista física, si solo hay un procesador y la vista del proceso si solo hay un proceso o programa. Para sistemas muy pequeños, incluso es posible que la vista lógica y la vista de desarrollo son tan similares que no requieren descripciones separadas. 

Los escenarios son útiles en todas las circunstancias.

Proceso iterativo

Witt et al, indican 4 fases para el diseño o para una arquitectura: bosquejar, organizar, especificar y optimización, subdividida en unos 12 pasos 7 . Indican que puede ser necesario dar marcha atrás. Nosotros pensamos que este enfoque es demasiado "lineal" para un proyecto ambicioso y sin precedentes. Se sabe muy poco en el final de las 4 fases para validar la arquitectura. Abogamos por un desarrollo más iterativo, si los En realidad, la arquitectura se crea un prototipo, se prueba, se mide, se analiza y luego se refina en iteraciones posteriores.

Además de permitir mitigar los riesgos asociados con la arquitectura, este enfoque tiene otro lado beneficios para el proyecto: team building, formación, conocimiento de la arquitectura, adquisición de herramientas, ejecución de procedimientos y herramientas, etc. (Estamos hablando aquí de un prototipo evolutivo, que lentamente se convierte en convertirse en el sistema, y ​​no en prototipos exploratorios desechables.) Este enfoque iterativo también permite los requisitos para ser refinados, maduros, mejor comprendidos.

Un enfoque basado en escenarios

La funcionalidad más crítica del sistema se captura en forma de escenarios (o casos de uso). Por crítico queremos decir: funciones que son las más importantes, la razón de ser del sistema, o que tienen la mayor frecuencia de uso, o que presenten algún riesgo técnico significativo que deba ser mitigado.

Comienzo:
  • Se elige una pequeña cantidad de escenarios para una iteración en función del riesgo y la criticidad. Escenarios puede sintetizarse para abstraer una serie de requisitos del usuario.
  • Se implementa una arquitectura de hombre de paja. Luego, los escenarios se "escriben" para identificar los principales abstracciones (clases, mecanismos, procesos, subsistemas) como lo indican Rubin y Goldberg 6 - descompuesto en secuencias de pares (objeto, operación).
  • Los elementos arquitectónicos descubiertos se establecen en los 4 planos: lógico, proceso, desarrollo y físico.
  • Esta arquitectura se implementa, prueba, mide y este análisis puede detectar algunas fallas o mejora potencial.
  • Se capturan las lecciones aprendidas.
Lazo:
    La siguiente iteración puede comenzar por:
  • reevaluar los riesgos,
  • ampliando la paleta de escenarios a considerar
  • seleccionar algunos escenarios adicionales que permitan la mitigación de riesgos o una mayor cobertura arquitectura
    Luego:
  • Intente escribir esos escenarios en la arquitectura preliminar
  • descubrir elementos arquitectónicos adicionales o, a veces, cambios arquitectónicos significativos que deben ocurrir para adaptarse a estos escenarios
  • actualizar los 4 planos principales: lógico, proceso, desarrollo, físico
  • revisar los escenarios existentes en función de los cambios
  • actualizar la implementación (el prototipo arquitectónico) para admitir el nuevo conjunto extendido de guión.
  • Prueba. Mida bajo carga, en el entorno objetivo real si es posible.
  • Luego, se revisan los cinco planos para detectar el potencial de simplificación, reutilización y similitud.
  • Se actualizan las pautas de diseño y la justificación.
  • Capture las lecciones aprendidas.
Ciclo final

El prototipo arquitectónico inicial evoluciona para convertirse en el sistema real. Con suerte, después de 2 o 3 iteraciones, la arquitectura misma se vuelve estable: no se encuentran nuevas abstracciones importantes, no hay nuevos subsistemas o procesos, no nuevas interfaces. El resto de la historia está en el ámbito del diseño de software, donde, por cierto, el desarrollo puede continúe usando métodos y procesos muy similares.

La duración de estas iteraciones varía considerablemente: con el tamaño del proyecto a implementar, con el número de personas involucradas y su familiaridad con el dominio y con el método, y con el grado de "sin precedentes" del sistema con esta organización de desarrollo. De ahí la duración de una iteración puede ser de 2 a 3 semanas para un proyecto pequeño (por ejemplo, 10 KSLOC) o de hasta 6 a 9 meses para un comando grande y sistema de control (por ejemplo, 700 KSLOC).

Documentando la arquitectura

La documentación producida durante el diseño arquitectónico se recoge en dos documentos:
  • Un Documento de Arquitectura de Software , cuya organización sigue de cerca las vistas “4 + 1” (ver fig. 13 para un esquema típico)
  • Una guía de diseño de software , que captura (entre otras cosas) el diseño más importante decisiones que deben respetarse para mantener la integridad arquitectónica del sistema

Conclusión

Este modelo de vista "4 + 1" se ha utilizado con éxito en varios proyectos grandes con o sin algunos personalización y ajuste de la terminología 4 . De hecho, permitió a las distintas partes interesadas encontrar lo que quiere saber sobre la arquitectura del software. Los ingenieros de sistemas lo abordan desde la vista física, luego la vista Proceso. Usuarios finales, clientes, especialistas en datos desde la vista lógica. Jefes de proyecto, software el personal de configuración lo ve desde la vista Desarrollo.

Se han propuesto y discutido otros conjuntos de puntos de vista, dentro de Rational y en otros lugares, por ejemplo Meszaros (BNR), Hofmeister, Nord y Soni (Siemens), Emery y Hilliard (Mitre) 8 , pero hemos encontrado que a menudo estos otros puntos de vista propuestos normalmente podrían plegarse en uno de los 4 que describimos. Por ejemplo una vista Costo y programa se pliega en la vista Desarrollo, una vista Datos en la vista Lógica, una Ejecución vista en una combinación de la vista de proceso y física.

Tabla 1 - Resumen del modelo de vista "4 + 1"

Expresiones de gratitud

El modelo de vista “4 + 1” debe su existencia a muchos colegas de Rational, en Hughes Aircraft of Canada, en Alcatel y otros lugares. En particular, me gustaría agradecer sus contribuciones al Cap. Thompson, A. Bell, M. Devlin, G. Booch, W. Royce, J. Marasco, R. Reitman, V. Ohnjec y E. Schonberg.

Referencias

1. D. Garlan & M. Shaw, "Una introducción a la arquitectura de software", Avances en software
Ingeniería e Ingeniería del conocimiento , vol. 1, World Scientific Publishing Co. (1993).

2. DE Perry y AL Wolf, "Fundamentos para el estudio de la arquitectura de software", ACM Software
Engineering Notes , 17 , 4, octubre de 1992, 40-52.

3. Ph. Kruchten & Ch. Thompson, “Una arquitectura distribuida orientada a objetos para Ada a gran escala Systems ”, Actas de la Conferencia TRI-Ada '94 , Baltimore, 6-11 de noviembre de 1994, ACM,
p.262-271.

4. G. Booch: Análisis y diseño orientado a objetos con aplicaciones , 2do. edición, Benjamin-Cummings Pub. Co., Redwood City, California, 1993, 589p.

5. KP Birman y R. Van Renesse, Computación distribuida confiable con el kit de herramientas de Isis, IEEE Computer Society Press, Los Alamitos CA, 1994.

6. K. Rubin y A. Goldberg, “Object Behavior Analysis” , MCCA , 35 , 9 (septiembre de 1992) 48-62

7. BI Witt, FT Baker y EW Merritt, Arquitectura y diseño de software: principios, modelos y
Methods , Van Nostrand Reinhold, Nueva York (1994) 324p.

8. D. Garlan (ed.), Actas del primer taller interno sobre arquitecturas para sistemas de software ,
CMU-CS-TR-95-151, CMU, Pittsburgh, 1995

DSN_XP y las Ciencias matemáticas de la computación

Hacia una ciencia matemática de Computación


DSN_XP recoge de la historia del software, los escritos que nos han parecido muy relevantes y dentro de este listado, en esta ocasión tomamos como referente la propuesta de John McCarthy denominada como Towards a Mathematical Science of Computation

Introducción (1996)

En este artículo discutiré las perspectivas de una ciencia matemática de computación. En una ciencia matemática, es posible deducir de los supuestos básicos, las propiedades importantes de las entidades tratadas por la Ciencia.  Así, a partir de la ley de gravitación de Newton y sus leyes del movimiento, uno puede deducir que las órbitas planetarias obedecen a las leyes de Kepler. 
  • ¿Cuáles son las entidades de las que se ocupa la ciencia de la computación? 
  • ¿Qué tipo de hechos sobre estas entidades nos gustaría derivar? 
  • ¿Cuáles son los supuestos básicos de los que debemos partir? 
  • ¿Qué resultados importantes se han obtenido ya? 
  • ¿Cómo puede la ciencia matemática ayudar en la solución de problemas prácticos?
Me gustaría proponer algunas respuestas parciales a estas preguntas. Estas respuestas parciales sugieren algunos problemas para el trabajo futuro. Primero, daré algunas respuestas generales muy esquemáticas a las preguntas. Entonces presentare algunos resultados recientes sobre tres cuestiones específicas. Finalmente, intentaré dibujar algunas conclusiones sobre aplicaciones prácticas y problemas para trabajos futuros. 

Este artículo debería considerarse junto con mi artículo anterior [McC63]. 

Los principales resultados del presente documento son nuevos, pero existe cierta superposición, por lo que este documento sería autónomo. Sin embargo, algunos de los temas de este escrito como expresiones condicionales, definición recursiva de funciones y prueba por inducción recursiva se consideran con mucho mayor detalle en el documento anterior.

¿Cuáles son las entidades con las que la ciencia del cómputo debe lidiar?

Estas son problemas, procedimientos, espacios de datos, programas que representan procedimientos en determinados lenguajes de programación y computadores. 

Los problemas y los procedimientos a menudo se confunden. 
  • Un problema se define por el criterio que determina si se acepta una solución propuesta. Uno puede comprender un problema completamente sin tener ningún método de solución.  
  • Los procedimientos generalmente se construyen a partir de procedimientos elementales. Lo qué pueden ser estos procedimientos elementales y cómo los procesos más complejos se construyen a partir de ellos, este es uno de los primeros temas de la ciencia de la computación
Esta temática no es difícil de entender desde que existe una noción precisa de una función computable para guiarnos y computablemente relativa a una colección dada de las funciones iniciales, es fácil de definirla.
  • Los procedimientos operan sobre miembros de ciertos espacios de datos y producen miembros de otros espacios de datos, utilizando en general otros espacios de datos como intermediarios. Se conocen varias operaciones para construir nuevos espacios de datos con los más simples, pero todavía no existe una teoría general de espacios de datos representables, comparables a la teoría de funciones computables. Algunos resultados están dados en [McC63].
  • Los programas son expresiones simbólicas que representan procedimientos. El mismo procedimiento puede estar representado por diferentes programas en diferentes lenguajes de programación.
Se discutirá el problema de definir semánticamente un lenguaje de programación indicando qué procedimientos representan los programas. En cuanto a la sintaxis de los lenguajes de programación, las reglas que nos permiten determinar si una expresión pertenece al lenguaje han sido formalizadas pero las partes de la sintaxis que se relacionan estrechamente con la semántica, no ha sido tan bien estudiadas

El problema de traducir procedimientos de un lenguaje de programación a otro ha sido muy estudiado y vamos a intentar dar una definición de la corrección de la traducción.

Las computadoras son autómatas finitos. Desde nuestro punto de vista, una computadora está definida por el efecto de ejecutar un programa con una entrada dada, en el estado de su memoria y de sus salidas.

La ciencia de la computación debe estudiar las diversas formas en la que los elementos de los espacios de datos se representan en memoria de la computadora y cómo los procedimientos están representados por programas de cómputo. Bajo esta perspectiva, la mayoría de los trabajos actuales sobre la teoría del autómata no viene al caso.

¿Qué tipos de hechos acerca de los problemas, procedimientos, espacios de datos, programas y computadores nos gustaría derivar?

Ante todo. nos gustaría poder demostrar que determinados procedimientos resuelven determinados problemas dados. Sin embargo, probar esto puede implicar probar una gran cantidad de otros tipos de afirmaciones como: 
  1. Dos procedimientos son equivalentes, por ejemplo, si calculan la misma función. 
  2. Varias funciones computables satisfacen una determinada relación, como una identidad algebraica o una fórmula del cálculo funcional. 
  3. Cierto procedimiento finaliza para ciertos datos iniciales, o para todos los datos iniciales. 
  4. Un cierto procedimiento de traducción, traduce correctamente los procedimientos entre un lenguaje de programación y otro. 
  5. Un procedimiento es más eficiente que otro procedimiento equivalente si en ese sentido se realiza en menos pasos o requiere menos memoria.
  6. Una cierta transformación de los programas conserva la función expresada pero aumenta la eficiencia.
  7. Cierta clase de problemas no se puede resolver mediante ningún procedimiento o requiere procedimientos de cierto tipo para su solución

¿Cuáles son los axiomas y reglas de inferencia de una ciencia matemática de computación?

Idealmente, nos gustaría una teoría matemática en la que todo enunciado verdadero acerca de los procedimientos tendría una prueba y preferiblemente una prueba que sea fácil de encontrar, no demasiado larga y fácil de comprobar. 

En 1931, Gödel demostró un resultado, uno cuyas consecuencias inmediatas fueron que no hay teoría matemáticas completa de la computación. Dada cualquier teoría matemática de la computación, hay enunciados verdaderos que pueden expresarse y que no tienen pruebas. Sin embargo, podemos esperar una teoría que sea adecuada para propósitos prácticos, como demostrar que los compiladores funcionan; las declaraciones no demostrables tienden a ser de un carácter bastante arrollador, como que el sistema en sí es consistente. 

Es casi posible hacerse cargo de uno de los sistemas de la teoría de los números elementales como la expuesta en el libro de Mostowski "Sentences Undecidable in Formalized Arithmetic" desde que el contenido de una teoría de la computación es bastante similar. Desafortunadamente, este y otros sistemas similares se diseñaron para facilitar la demostración de meta teoremas sobre el sistema, en lugar de probar teoremas en el sistema. Como resultado, a los enteros se les dio un papel tan especial que pruebas de afirmaciones bastante fáciles sobre procedimientos simples podrían ser extremadamente largas.

Por lo tanto, es necesario construir un nuevo pensamiento similar, teoría en la que ni los números enteros, ni ningún otro dominio (por ejemplo, cadenas de símbolos) se les de un papel especial. Se describen algunos resultados parciales en esta dirección en este escrito. A saber, un formalismo libre de números enteros para describir cálculos ha sido desarrollado y ha demostrado ser adecuado en los casos en que los que puede ser comparado con otros formalismos. 

Se han desarrollado algunos métodos de prueba, pero todavía existe una brecha en lo que respecta a los métodos para demostrar que un procedimiento finaliza. La teoría también requiere extensión para tratar las propiedades de los espacios de datos.

¿Qué resultados relevantes se han obtenido para una ciencia matemática de computación?

En 1936, Turing aclaró la noción de función computable y demostró la existencia de computadores universales que, con un adecuado programa, podría calcular cualquier cosa calculada por cualquier otra computadora. 

Todo nuestros programas almacenados de computadoras, cuando se les proporciona almacenamiento auxiliar ilimitado, son universales, en el sentido de Turing. En cierto sentido subconsciente, incluso las ventas de los departamentos de los fabricantes de computadoras son conscientes de esto y no anuncian instrucciones mágicas que no pueden ser simuladas en máquinas competidoras, pero solo se anuncia que sus máquinas son más rápidas, más baratas, tienen más memoria, o son más fáciles de programar. 

El segundo resultado importante fueron la existencia de clases de problemas irresolubles. Esto mantiene a todas las empresas menos a las más ignorantes de nosotros tratando de inventar un procedimiento de depuración que pueda infaliblemente decir si un programa que se está examinando entrará en un bucle. 

Más adelante en este escrito, discutiremos la relevancia de los resultados de la lógica matemática a un grupo de problemas creativos sobre si es posible que la máquina pueda ser tan inteligente como un ser humano. En mi opinión es muy importante construir un puente más firme entre la lógica y la teoría de funciones recursivas por un lado y la práctica de la computación por el otro. 

Gran parte del trabajo sobre la teoría de los autómatas finitos ha sido motivado con la esperanza de aplicarlo en la computación. Pienso que esta esperanza en su mayoría es en vano porque el hecho de la finitud se usa para mostrar que el autómata eventualmente repetirá un estado. Sin embargo, cualquiera que espere que un IBM 7090 repita un estado, únicamente porque es un autómata finito, está en una espera muy larga.

¿Cómo puede la ciencia matemática de la computación ayudar a la solución práctica de problemas?

Naturalmente, no se pueden prever las aplicaciones más importantes de una ciencia cuando recién comienza. Sin embargo, se pueden prever las siguientes aplicaciones: 
  1. En la actualidad, los lenguajes de programación se construyen de una manera muy poco sistemática. Se inventan una serie de características propuestas y luego argumentamos sobre si cada función vale su costo. Una mejor comprensión de la estructura de los cálculos y de los espacios de datos facilitará ver qué las características son realmente deseables. 
  2. Debería ser posible casi eliminar la depuración. La depuración son las pruebas de un programa en los casos que uno espera sean típicos, hasta que parece que funcionan.  Esta esperanza es frecuentemente vana. 
En lugar de depurar un programa, se debe demostrar que cumple con sus especificaciones y esta prueba debe ser verificada por un programa de computadora. Para que esto sea posible, se requieren sistemas formales en los que sea fácil escribir pruebas.

Hay una buena posibilidad de hacer esto, porque podemos requerir de la computadora hacer mucho más trabajo en la verificación de cada paso de lo que un humano está dispuesto a hacer. Por lo tanto, los pasos pueden ser mayores que con los sistemas formales actuales. las perspectivas para esto se discuten en [McC62].

El uso de expresiones condicionales para definir funciones recursivas

En el lenguaje matemático ordinario, existen ciertas herramientas para definir nuevas funciones en términos de las antiguas. Estas herramientas son la composición y la identificación de variables. Da la casualidad de que estas herramientas son inadecuadas computablemente en términos de las anteriores. Entonces se acostumbra definir todas las funciones que pueden razonablemente considerarse que dan una definición verbal. Por ejemplo, la función | x | generalmente se define en palabras. 

Si agregamos una sola herramienta formal, a saber, expresiones condicionales a nuestra notación matemática y si permitimos que se utilicen expresiones condicionales recursivamente de una manera que pueda describirse, podemos definir, de una manera completamente formal, todas las funciones que razonablemente pueden considerarse computables en términos de un conjunto inicial. 

Usaremos la notación ALGOL 60 para expresiones condicionales en este documento. 

Usaremos expresiones condicionales en la forma simple 

si p entonces a si no b 

donde p es una expresión proposicional cuyo valor es verdadero o falso. El valor de la expresión condicional es a si p tiene el valor verdadero y b si p tiene el valor falso. Cuando se utilizan expresiones condicionales, el stock de predicados que uno tiene disponible para construir p es tan importante como el stock de funciones ordinarias que se utilizarán para formar las a y las b por composición. 

A continuación, se muestran ejemplos de funciones definidas por expresiones condicionales:


La primera de ellas es la única definición no recursiva del grupo. Luego, tenemos tres procedimientos diferentes para calcular n !; les puede parecer ser equivalentes por los métodos que se describirán en este documento. Entonces definimos la función predecesora n- para enteros positivos (3- = 2) en términos de la función sucesora n´(2´ = 3) Finalmente, definimos la suma en términos del sucesor, antecesor e igualdad. En todas las definiciones, excepto en la primera, el dominio de las variables se toma como el conjunto de valores no negativos enteros.

Como ejemplo del uso de estas definiciones, mostraremos cómo computar 2! según la segunda definición de n !. Tenemos


Tenga en cuenta que si intentamos calcular n! para cualquier n pero entero no negativo las sucesivas reducciones no terminarían. En tales casos decimos que el cálculo no converge. Algunas funciones recursivas convergen para todos los valores de sus argumentos, algunas convergen para algunos valores de sus argumentos y algunos nunca convergen. Las funciones que siempre convergen se llaman funciones totales, y las otras se llaman funciones parciales. Uno de los resultados más importantes de la teoría de la función recursiva es que no hay formalismo que obtenga todas las funciones totales computables y no funciones parciales.

[McC63] Hemos probado que el método anterior para definir funciones computables, comenzando solo con la función sucesora n` y la igualdad, produce todas las funciones computables de los enteros. Esto nos lleva a afirmar que tenemos el conjunto completo de herramientas para definir funciones que son computables en términos de las dadas funciones base.

Si examinamos la penúltima línea de nuestro cálculo de 2! vemos eso no podemos simplemente considerar la expresión condicional 

si p entonces a si no b 

como función de las tres cantidades p, a y b. Si lo hiciéramos, estaríamos obligados a calcular g (−1,0) antes de evaluar la expresión condicional y este cálculo no convergería. Lo que debe pasar es que cuando p es cierto, tomamos a como el valor de la expresión condicional sin regresar a ver a b.

Cualquier referencia a funciones recursivas en el resto de este artículo se refiere a funciones definidas por los métodos anteriores. 

Probar afirmaciones sobre funciones recursivas

En la sección anterior presentamos un formalismo para dadas funciones base describir funciones que son computables en términos de estas. Nos gustaría tener una teoría matemática lo suficientemente fuerte como para admitir pruebas de esos hechos acerca de los procedimientos de computación que uno normalmente necesita para mostrar que los programas computables cumplen con sus especificaciones. 

En [McC63] mostramos que nuestro formalismo para expresar funciones computables, era lo suficientemente fuerte como para que todos las funciones recursivas de enteros se pueden obtener a partir de la función sucesora y la igualdad. Ahora nos gustaría una teoría lo suficientemente fuerte para que la adición de alguna forma de axiomas de Peano permitiría la demostración de todos los teoremas de una de las formas de la teoría de números elementales. 

Aún no tenemos tal teoría. La dificultad radica en mantener los axiomas y reglas de inferencia de la teoría libres de los enteros u otros dominios, tal como lo hemos logrado con el formalismo para construir funciones.  Ahora enumeraremos las herramientas que tenemos hasta ahora para probar las relaciones entre funciones recursivas. Se comentan con más detalle en [McC63]. 
  1. Sustitución de expresiones por variables libres en ecuaciones y otras relaciones. 
  2. Reemplazo de una subexpresión en una relación por una expresión que se ha demostrado que es igual a la subexpresión. (Esto se conoce en matemáticas elementales como sustitución de iguales por iguales.)

    Cuando estamos tratando con expresiones condicionales, una forma de esta regla más fuerte que la habitual es válida. Supongamos que tenemos una expresión de la forma

     si p entonces a si no (si q entonces b si no c) 

    y deseamos reemplazar b por d. En estas circunstancias, no tenemos que probar la ecuación b = d en general, pero solo el enunciado más débil

    ∼ p ∧ q ⊃ b = d

    Esto se debe a que b afecta el valor de la expresión condicional solo en el caso ∼ p ∧ q es cierto. 
  3. Las expresiones condicionales satisfacen una serie de identidades y una teoría completa de las expresiones condicionales, muy similar al cálculo proposicional, es tratada a fondo en [McC63]. Enumeraremos algunas de las identidades tomadas como axiomas aquí. 



  4. Finalmente, tenemos una regla llamada inducción de recursividad para hacer argumentos que en las formulaciones habituales se realizan por inducción matemática. Esta regla puede considerarse que toma uno de los teoremas de la teoría de la función recursiva y dándole el estatus de regla de inferencia. Inducción de recursividad puede describirse de la siguiente manera:

    Supongamos que tenemos una ecuación de recursión que define una función f, a saber

  5. f (x 1 , ..., x n ) = ε {f, x 1 , ..., x n } (1)

    donde el lado derecho será una expresión condicional en todos los no triviales casos y supongamos que:

    1. El cálculo de f (x 1 , ..., x n ) de acuerdo con esta regla converge para un cierto conjunto A de n-tuplas, 
    2. las funciones g (x 1 , ..., x n ) y h (x 1 , ..., x n ) satisfacen cada una la ecuación (1) cuando g o h se sustituye por f.  Entonces podemos concluir que g (x 1 , ..., x n ) = h (x 1 , ..., x n ) para todas las n-tuplas (x 1 , ..., x n ) del conjunto A. 

    Como ejemplo del uso de la inducción recursiva demostraremos que la función g definida por 

    g (n, s) = si n = 0 entonces s si no g (n - 1, n × s) 

    satisface g (n, s) = n! × s dados los datos habituales sobre n !, Tomaremos por dado el hecho de que g (n, s) converge para todas las integrales n y s no negativas. Entonces solo necesitamos mostrar que n! × s satisface la ecuación para g (n, s), tenemos

    n! × s = si n = 0 entonces n! × s else n! × s 
                  si n = 0 entonces s else (n - 1)! × (n × s) 

    y esto tiene la misma forma que la ecuación satisfecha por g (n, s). Los pasos en esta derivación son bastante obvios pero también siguen los axiomas mencionados anteriormente y las reglas de inferencia.  En particular, la regla extendida de reemplazo se utilizan varios ejemplos adicionales de demostración por inducción de recursividad se dan en [McC63] y se ha utilizado para probar algunas relaciones bastante complicadas entre funciones computables.

Funciones recursivas, diagramas de flujo y programas algolic

En esta sección quiero establecer una relación entre el uso de funciones recursivas para definir cálculos, la notación del diagrama de flujo y programas expresados como una secuencia de sentencias de asignación de tipos ALGOL, junto con la condicional Go To. A este último lo llamaremos programas Algolic con la idea de ampliar posteriormente la notación y los métodos de prueba para cubrir más el lenguaje ALGOL. Recuerda que nuestro propósito aquí no es crear todavía otro lenguaje de programación, sino proporcionar herramientas para probar hechos sobre programas

Para considerar los programas como funciones recursivas, definiremos el estado del vector ξ de un programa en un momento dado, para ser el conjunto de valores actualmente asignados a las variables del programa. En el caso de un programa en lenguaje de máquina, el estado del vector es el conjunto de contenidos actuales de esos registros cuyo contenido cambia durante el curso de la ejecución del programa. 

Cuando se ejecuta un bloque de programa que tiene una sola entrada y salida, el efecto de esta ejecución en el estado del vector puede ser descrito por una función ξ` = r (ξ) dando el nuevo estado del vector en términos del antiguo. 

Considere un programa descrito por el diagrama de flujo de la fig. 1.


Los dos bloques internos de cómputo se describen mediante las funciones f (ξ) y g (ξ), indicando cómo estos bloques afectan el estado del vector. Los óvalos de decisión se describen mediante los predicados p (ξ), q 1 (ξ) y q 2 (ξ) que define las condiciones para tomar varios caminos. Deseamos describir la función r (ξ) que da el efecto a todo el bloque, en términos de las funciones f y g y los predicados p, q 1 y q 2 . Esto se hace con la ayuda de dos funciones auxiliares s y t. s (ξ) describe el cambio en ξ entre el punto etiquetado como s en el gráfico y la salida final del bloque; t se define de manera similar con respecto al punto etiquetado t. Podemos leer las siguientes ecuaciones directamente del diagrama de flujo:

r (ξ) = s (f (ξ))
s (ξ) = si p (ξ) entonces r (ξ) si no t (g (ξ))
t (ξ) = si q 1 (ξ) entonces r (ξ) si no q 2 (ξ) entonces ξ si no t (g (ξ))

De hecho, estas ecuaciones contienen exactamente la misma información que el diagrama de flujo.

Considere la función mencionada anteriormente, dada por

g (n, s) = si n = 0 entonces s si no g (n - 1, n × s)

Corresponde, como dejamos que el lector se convenza a sí mismo, al programa Algolic 

Este diagrama de flujo se muestra en la fig. 2.

En el diagrama de flujo se describe mediante la función fac (ξ) y la ecuación 

fac (ξ) = si p (ξ) entonces ξ si no fac (g (f (ξ)))

donde p (ξ) corresponde a la condición n = 0, f (ξ) al enunciado n: = n - 1 y 
g (ξ) al enunciado s: = n × s.


dónde

p (ξ) ≡ c (n, ξ) = 0,

f (ξ) = a (s, c (n, ξ) ∗ c (s, ξ), ξ),

g (ξ) = a (n, c (n, ξ) - 1, ξ)

y así
fac (ξ) = a (n, 0, a (s, c (n, ξ)! × c (s, ξ))).

Consideraremos que el estado del vector tiene muchos componentes, pero los únicos componentes afectados por el presente programa son el componente s y el componente n. 

Para calcular explícitamente con los estados del vector, introducimos la función c (var, ξ) que denota el valor asignado a la variable var en el estado del vector ξ, y también introducimos la función a (var, val, ξ) que denota el estado del vector que resulta cuando el valor asignado a var en ξ se cambia a val y los valores de las otras variables no se modifican.

Los predicados y funciones de los estados del vector mencionados anteriormente serían:

p (ξ) = (c (n, ξ) = 0)

g (ξ) = a (n, c (n, ξ) - 1, ξ)

f (ξ) = a (s, c (n, ξ) × c (s, ξ), ξ)

Podemos probar por inducción de recursividad que fac (ξ) = a (n, 0, a (s, c (n, ξ)! × c (s, ξ), ξ),
pero para hacerlo debemos utilizar los siguientes hechos sobre las funciones del estado básico del vector:
  1. c (u, a (v, α, ξ)) = si u = v entonces α si no c (u, ξ)
  2. a (v, c (v, ξ), ξ) = ξ
  3. a (u, α, a (v, β, ξ)) = si u = v entonces a (u, α, ξ) de lo contrario a (v, β, a (u, α, ξ))
    La prueba es paralela a la prueba anterior de que
    g (n, s) = n! × s,
pero las fórmulas son más largas.

Si bien todos los diagramas de flujo corresponden inmediatamente a funciones recursivas de el estado del vector, lo contrario no es el caso. La traducción desde la función recursiva al diagrama de flujo y por lo tanto al programa Algolic es inmediata, sólo si las ecuaciones de recursividad están en forma iterativa. Supongamos que tenemos una ecuación de recursividad

r (x 1 , ..., x n ) = E {r, x 1 , ..., x n , f 1 , ..., f m }

donde E {r, x 1 , = ldots, x n , f 1 , ..., f m } es una expresión condicional que define la función r en términos de las funciones f 1 , ..., f m . Se dice que E está en modo iterativo si r nunca aparece como el argumento de una función, sino sólo en términos de expresión condicional principal en la forma

... luego r (...).

En los ejemplos, todas las definiciones recursivas excepto

n! = si n = 0 entonces 1 si no n × (n - 1)!

están en forma interactiva. En ese, (n - 1)! ocurre como un término de un producto. 

Las funciones recursivas no iterativas se traducen en programas Algolic que se utiliza recursivamente como procedimiento. Los cálculos numéricos generalmente pueden transformarse en forma iterativa, pero los cálculos con expresión simbólica usualmente no pueden, a menos que las cantidades que juegan el papel de listas introducido explícitamente.

Inducción de recursividad en programas Algolic

En esta sección ampliamos el principio de inducción de recursividad para que pueda aplicarse directamente a los programas de Algolic sin antes transformarlos en funciones recursivas. Considere el programa Algolic 
Queremos demostrar que es equivalente al programa 

Antes de dar esta prueba describiremos el principio de inducción de recursividad tal como se aplica a una clase simple de diagramas de flujo. Supongamos que tenemos un bloque de programa representado por la fig. 3a. Supongamos que hemos probado que este bloque es equivalente al diagrama de flujo de la fig. 3b donde el bloque sombreado es el bloque original de nuevo. Esto corresponde a la idea de una función que satisface una ecuación funcional. Ahora podemos concluir que el bloque de la fig. 3a es equivalente al diagrama de flujo de la fig. 3c para aquellos estados del vector para los que el programa no quede atascado en un bucle en la fig. 3c. 


Esto se puede ver de la siguiente manera, suponga que, para una entrada particular, el programa de la fig. 3c da la vuelta al bucle n veces antes de salir. Considere el diagrama de flujo que resulta cuando toda la fig. 3b se sustituye por el bloque sombreado (o amarillo) y luego sustituido en esta figura nuevamente, etc., un total de n sustituciones. El estado del vector al pasar por este diagrama de flujo se someterá exactamente a las mismas pruebas y cambios que al pasar por el flujo. 3c y, por lo tanto, saldrá en n pasos sin pasar por el bloque sombreado (o amarillo). Por tanto, debe salir con el mismo valor como en la fig. 3c. Por lo tanto, para cualquier vector para el que el cálculo de la fig. 3c converge, fig. 3a es equivalente a la fig. 3c.

Por tanto, para utilizar este principio para demostrar la equivalencia de dos bloques, probamos que satisfacen la misma relación, de tipo 3a-3b, y que el 3c correspondiente converge.

Aplicaremos este método para demostrar que los dos programas mencionados anteriormente son equivalentes. El primer programa se puede transformar de la siguiente manera:


La operación utilizada para transformar el programa es simplemente escribir por separado la primera ejecución de un bucle.

En el caso del segundo programa vamos:


Las operaciones utilizadas aquí son: primero, la introducción de una rama espuria, después de lo cual se realiza la misma acción independientemente de la forma en que la rama vaya; segundo, una simplificación basada en el hecho de que si la rama va por la primera vía, luego n = 0, junto con la reescritura de uno de los lados derechos de una declaración asignada y tercero, eliminación de una etiqueta correspondiente a una declaración nula y lo que podría llamarse una anti-simplificación de una secuencia de declaraciones de asignación. Aún no hemos elaborado un conjunto de reglas formales que justifique estos pasos, pero las reglas se pueden obtener de las reglas dadas anteriormente para sustitución, reemplazo y manipulación de expresiones condicionales. 

El resultado de estas transformaciones es mostrar que los dos programas, satisface cada uno una relación de la forma: programa es equivalente a


El programa correspondiente a la fig. 3c en este caso, es precisamente el primer programa que asumiremos siempre converge. Esto completa la prueba.

La descripción de los lenguajes de programación

Los lenguajes de programación deben describirse sintácticamente y semánticamente. Esta es la distinción. La descripción sintáctica incluye: 
  1. Una descripción de la morfología, es decir, qué expresiones simbólicas representan programas gramaticales. 
  2. Las reglas para el análisis de un programa en partes y su síntesis de las partes. Por tanto, debemos ser capaces de reconocer un término que represente un suma y extraer de ella los términos que representan los sumandos. 
La descripción semántica del lenguaje debe decir lo que los programas significan. El significado de un programa es su efecto sobre el estado del vector en el caso de un lenguaje independiente de la máquina, y su efecto sobre el contenido de la memoria en el caso de un programa en lenguaje máquina.

Sintaxis abstracta de los lenguajes de programación

La forma normal de Backus que se utiliza en el informe ALGOL describe la morfología de los programas ALGOL de forma sintética. Es decir, describe cómo se construyen los distintos tipos de programas a partir de sus partes. Esto sería mejor para traducir a ALGOL que para el problema más habitual de traducir desde ALGOL. 

La forma de sintaxis que describiremos ahora difiere de la forma normal de Backus de dos maneras. Primero, es analítico en lugar de sintético; dice cómo desarmar un programa, en lugar de cómo armarlo. En segundo lugar, es abstracto en el sentido de que es independiente de la notación utilizada para su representación, digamos sumas, pero solo afirma que pueden ser reconocidas y desmontadas.

Considere un fragmento de los términos aritméticos de ALGOL, incluidas las constantes y las variables y sumas y productos. Como simplificación adicional, se debe considerar que las sumas y los productos tienen exactamente dos argumentos, aunque el caso general no es muy difícil. Supongamos que tenemos un término t. Desde la perspectiva de traducción, primero debemos determinar si representa una constante, una variable, una suma o un producto. Por lo tanto, postulamos la existencia de cuatro predicados: isconst (t), isvar (t), issum (t) e isprod (t). Supondremos que cada término satisface exactamente uno de estos predicados. 

Considere los términos que son variables. Un traductor deberá poder saber si dos símbolos son ocurrencias de la misma variable, por lo que necesitamos un predicado de igualdad en el espacio de variables. Si las variables tienen que ser ordenadas se requiere una relación de ordenación. 

Considere las sumas. Nuestro traductor debe poder seleccionar los sumandos y por lo tanto postulamos la existencia de funciones addend (t) y augend (t) definidas en aquellos términos que satisfacen issum (t). Del mismo modo, tenemos las funciones mplier (t) y mpcand (t) definidas en los productos. Desde el análisis de un término debe terminar, el predicado definido recursivamente


debe converger y tener el valor verdadero para todos los términos.

Los predicados y funciones cuya existencia y relaciones definen la sintaxis, son precisamente las necesarias para traducir del lenguaje, o para definir la semántica. Por eso no es necesario que nos importe si las sumas están representadas por a + b, o + ab, o (PLUS AB), o incluso por los números de Gödel 7 a 11 b .

Es útil considerar lenguajes que tienen tanto una analítica como una sintaxis sintética que satisface ciertas relaciones. Continuando con nuestro ejemplo de términos, la sintaxis sintética está definida por dos funciones mksum(t, u) y mkprod (t, u) que, cuando se dan dos términos t y u, dan su suma y producto respectivamente.  Llamaremos regular a la sintaxis si las sintaxis analítica y sintética están relacionadas por las relaciones plausibles:


Una vez que se ha decidido la sintaxis abstracta de un lenguaje, se puede elegir el dominio de las expresiones simbólicas que se utilizarán. Entonces uno puede definir las funciones sintácticas explícitamente y se satisfacen a si mismas, preferiblemente probando que satisfagan las relaciones adecuadas. Si tanto el analítico como el sintético se dan funciones, no tenemos las difíciles y a veces insolubles problemas de análisis que surgen cuando los lenguajes se describen sólo sintéticamente.

En ALGOL las relaciones entre las funciones analítica y sintética no son del todo regulares, es decir, las relaciones sólo se mantienen hasta una equivalencia. Por tanto, se permiten paréntesis redundantes, etc.

Semántica

Las funciones sintácticas analíticas se pueden utilizar para definir la semántica de un lenguaje de programación. Para definir el significado de los términos aritméticos descritos anteriormente, necesitamos dos funciones más de naturaleza semántica, uno analítico y otro sintético. Si el término t es una constante, entonces val (t) es el número que t denota. Si α es un número mkconst (α) es la expresión simbólica que denota este número. Tenemos las relaciones obvias 
  1. val (mkconst (α)) = α
  2. isconst (mkconst (α))
  3. isconst (t) ⊃ mkconst (val (t)) = t
Ahora podemos definir el significado de los términos diciendo que el valor de un término para un vector de estado ξ viene dado por 


Podemos ir más lejos y describir el significado de un programa en un lenguaje de programación de la siguiente manera: El significado de un programa se define por su efecto en el estado del vector. Es cierto que esta definición deberá elaborarse para tener en cuenta la entrada y la salida. 

En el caso de ALGOL deberíamos tener una función

ξ = algol (π, ξ), 

que da el valor ξ del vector de estado después de que el programa ALGOL π se haya detenido, dado que se inició al principio y que el vector de estadoin icialmente era ξ. Esperamos publicar en otro lugar una descripción recursiva del significado de un pequeño subconjunto de ALGOL. 

Las reglas de traducción también se pueden describir formalmente. A saber,
  1. Una máquina se describe mediante una función
    x = máquina (p, x)
    dando el efecto de operar el programa de máquina p en un vector de máquina x.
  2. Una representación invertible x = rep (ξ) de un vector de estado como una máquina se da el vector.
  3. Una función p = trans (π) que traduce programas fuente a máquina se dan programas.
    La exactitud de la traducción se define por la ecuación

    rep (algol (π, ξ)) = máquina (trans (π), rep (ξ)). 
Cabe señalar que trans (π) es una función abstracta y no un programa de máquina . Para describir los compiladores, necesitamos otra función abstracta invertible , u = repp (π), que da una representación del programa fuente en la memoria de la máquina lista para ser traducida. Un compilador es entonces un programa de máquina tal que trans (π) = máquina (compilador, repp (π)).

Las limitaciones de las máquinas y los hombres como solucionadores de problemas

¿Puede un hombre hacer un programa de computadora que sea tan inteligente como él? La pregunta tiene dos partes. Primero, preguntamos si es posible en principio, en vista de los resultados matemáticos sobre indecidibilidad e incompletitud, la segunda parte es una cuestión del estado de la programación en lo que respecta a inteligencia artificial. Incluso si la respuesta a la primera pregunta es "no", uno todavía puede intentar llegar lo más lejos posible en la resolución de problemas por máquina.

Supongo que, en principio, no existe tal limitación. Sin embargo, la discusión completa involucra las partes más profundas de la teoría de la función recursiva y no se han desarrollado todas las matemáticas necesarias.

Considere el problema de decidir si una oración de cálculo bajo de predicados es un teorema. Muchos problemas de las matemáticas actuales o de interés científico puede formularse de esta forma y ​​este problema resulta equivalente a muchos otros problemas, incluido el problema de determinar si un programa en una computadora con memoria ilimitada se detendrá alguna vez. 

Según Post, esto equivale a decidir si un número entero es un miembro de lo que Post llama un conjunto creativo. Myhill demostró que todo conjunto creativo es equivalentes en un sentido bastante fuerte, de modo que en realidad sólo hay un clase de problemas en este nivel de insolubilidad.

Sobre este problema se conocen los siguientes hechos:
  1. Existe un procedimiento que hará lo siguiente: Si el número está en el conjunto creativo, el procedimiento dirá "sí" y si el número no está en el conjunto creativo, el procedimiento no dirá "sí", puede decir "no" o puede ejecutarse de forma indefinida.
  2. No existe un procedimiento que siempre diga "sí" cuando la respuesta es "sí", y siempre dirá "no" cuando la respuesta sea "no", si un procedimiento tiene la propiedad (1) que a veces debe ejecutarse indefinidamente. Por tanto, no hay procedimiento que siempre puede decidir definitivamente si un número es miembro de un conjunto creativo, o de manera equivalente, si una oración del predicado inferior el cálculo es un teorema, o si un programa ALGOL con una entrada dada nunca parará. Este es el sentido en el que estos problemas no tienen solución.
  3. Ahora llegamos al sorprendente resultado de Post. Podríamos intentar hacerlo también como sea posible. Es decir, podemos intentar encontrar un procedimiento que siempre diga "sí" cuando la respuesta es "sí", y nunca dice "sí" cuando la respuesta es "no" y que dice "no" para una clase tan grande de casos negativos como sea posible, por lo tanto delimitando el conjunto de casos en los que el procedimiento continúa indefinidamente tanto como podamos. Post demostró que ni siquiera se puede hacer lo mejor posible. Es decir, Post dio un procedimiento que, al recibir cualquier otra decisión parcial procedimiento, daría uno mejor. El mejor procedimiento decide todos los casos el primer procedimiento decidido, y una clase infinita de nuevos. Primero vista esto parece sugerir que Emil Post era más inteligente que cualquier otro posible máquina, aunque el propio Post se abstuvo modestamente de dibujar este conclusión. Cualquiera que sea el programa que proponga, Post puede hacerlo mejor. Sin embargo, esto es injusto para los programas. A saber, el procedimiento de mejora de Post es en sí mismo mecánico y puede llevarse a cabo por máquina, de modo que la máquina puede mejorar su propio procedimiento o incluso puede mejorar la publicación, si se le da una descripción de los propios métodos de Post para tratar de decidir oraciones del predicado inferior cálculo. Es como un concurso para ver quién puede nombrar el mayor número. El hecho de que pueda sumar uno a cualquier número que des, no prueba que sea mejor que tu.
  4. Sin embargo, la situación es más complicada que esto. Obviamente, el proceso de mejora puede llevarse a cabo un número finito de veces y poco pensamiento muestra que el proceso se puede llevar a cabo un número infinito de veces. Es decir, sea p el procedimiento original y la mejora de Post procedimiento se llamará P, entonces P n p representa el procedimiento original mejorado n veces. Podemos definir P ω p como un procedimiento que aplica p durante un tiempo, luego P D por un tiempo, luego p nuevamente, luego P p , luego P 2 p, luego p, luego P p , luego P 2 p, entonces P 3 p, etc. Este procedimiento decidirá cualquier problema que cualquier P n voluntad decidir, por lo que con razón puede llamarse P ω p. Sin embargo, P ω p es en sí mismo sujeto al proceso de mejora original de Post y el resultado puede llamarse P ω + 1 p. ¿Hasta dónde puede llegar esto? La respuesta es técnica. Es decir, dado cualquier recursivoα ordinal transfinito, se puede definir P α p. Un ordinal recursivo es un recursivo ordenamiento de los enteros que es un buen ordenamiento en el sentido de que cualquier subconjunto delos números enteros tienen un miembro mínimo en el sentido del orden. Por lo tanto, tenemos un concurso para tratar de nombrar el ordinal recursivo más grande. Aquí parece que estamos atascado, porque el límite de los ordinales recursivos no es recursivo. Sin embargo, esto no excluye la posibilidad de que haya una mejora diferente proceso Q, de modo que Qp es mejor que P α p para cualquier α ordinal recursivo.
  5. Hay otra complicación más. Suponga que alguien nombra lo que reclamaciones es un gran ordinal recursivo. Nosotros, o nuestro programa, podemos nombrar un agregando uno, pero ¿Cómo sabemos que el procedimiento que él afirma es un ordenamiento recursivo, ¿de verdad? Dice que lo ha probado en algún sistema de la aritmética. En primer lugar, puede que no estemos seguros de que su sistema dela aritmética es correcta o incluso consistente. Pero incluso si el sistema es correcto, según el teorema de Gödel, está incompleto. En particular, hay ordinales que no se puede probar que sean así en ese sistema. Rosenbloom, en su libro "Elementos de lógica matemática" llegó a la conclusión de que el hombre era en principio superior a las máquinas porque, dado cualquier sistema formal de aritmetica, podría dar un sistema más fuerte que contenga oraciones verdaderas y probables eso no se pudo probar en el sistema original. Lo que Rosenbloom se perdió presumiblemente por razones sentimentales, es que el procedimiento de mejora es en sí mismo mecánico, y sujeto a iteración a través de los ordinales recursivos, por lo queque estamos de vuelta en la gran carrera ordinal. De nuevo nos enfrentamos a la complicación de probar que nuestros grandes ordinales son realmente ordinales.
  6. Estas consideraciones tienen poca importancia práctica en su presente formar. Es decir, el proceso de mejora original es tal que la mejora Es probable que el proceso sea demasiado lento para obtener resultados en un tiempo razonable, ya sea realizado por el hombre o por la máquina. Sin embargo, puede ser posible poner este jerarquía en alguna forma utilizable. Para concluir, permítanme reafirmar que la cuestión de si existen limitaciones en principio de los problemas que el hombre puede hacer que las máquinas resuelvan comparado con su propia capacidad para resolver problemas, realmente es una técnica pregunta en la teoría de la función recursiva.

Referencias

[McC62] John McCarthy. Verificación de pruebas matemáticas por computadora. En Proceedings Symposium on Recursive Function Theory (1961). Sociedad Americana de Matemáticas, 1962.

[McC63] J. McCarthy. Una base para una teoría matemática de la computación. 1 en
P. Braffort y D. Hirschberg, editores, Programación informática y Sistemas formales, páginas 33–70. Holanda Septentrional, Amsterdam, 1963