Redes de procesadores de empalme uniforme: potencia computacional y simulación
Autores: Gómez-Canaval, Sandra; Mitrana, Victor; Pun, Mihaela; Sanchez Martín, José Angel; Sánchez Couso, José Ramón
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Redes de procesadores de empalme uniforme: potencia computacional y simulación
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Potencia computacional
Red de procesadores de empalme
Variante
Comunicación
Máquinas de Turing
Simulación
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 31
Citaciones: Sin citaciones
Investigamos el poder computacional de una nueva variante de red de procesadores de empalme, que simplifica el modelo general de manera que los filtros permanecen asociados con los nodos, pero los filtros de entrada y salida de cada nodo coinciden. Esta variante, llamada, podría implementarse de manera más sencilla. Aunque la comunicación en la nueva variante parece menos potente, la nueva variante es lo suficientemente potente como para ser computacionalmente completa. Por lo tanto, las máquinas de Turing no deterministas fueron simuladas por redes de procesadores de empalme uniformes cuyo tamaño depende linealmente del alfabeto de la máquina de Turing. Además, la simulación fue eficiente en tiempo. Sostenemos que el tamaño de la red puede reducirse a una constante, concretamente seis nodos. Mostramos además que las redes con solo dos nodos pueden simular sistemas de 2 etiquetas. Tras estos resultados teóricos, discutimos una posible implementación de software de este modelo proponiendo una arquitectura conceptual y describiendo todos sus componentes.
Descripción
Investigamos el poder computacional de una nueva variante de red de procesadores de empalme, que simplifica el modelo general de manera que los filtros permanecen asociados con los nodos, pero los filtros de entrada y salida de cada nodo coinciden. Esta variante, llamada, podría implementarse de manera más sencilla. Aunque la comunicación en la nueva variante parece menos potente, la nueva variante es lo suficientemente potente como para ser computacionalmente completa. Por lo tanto, las máquinas de Turing no deterministas fueron simuladas por redes de procesadores de empalme uniformes cuyo tamaño depende linealmente del alfabeto de la máquina de Turing. Además, la simulación fue eficiente en tiempo. Sostenemos que el tamaño de la red puede reducirse a una constante, concretamente seis nodos. Mostramos además que las redes con solo dos nodos pueden simular sistemas de 2 etiquetas. Tras estos resultados teóricos, discutimos una posible implementación de software de este modelo proponiendo una arquitectura conceptual y describiendo todos sus componentes.