Presidential Young Investigator Award: Theory of Computing Machinery

这项研究计划的目标是了解限制， 计算硬件的能力。 发现新的计算 架构和算法是另一个目标， 而数学证明是所使用的方法论。 工作重点是 并行计算机编程的问题。 本研究探讨如何 基于胖树的并行超级计算机，一类新的 通用路由网络，可以合理地编程。 的 长期目标是建立一个“元循环评估器”， Lisp解释器或通用图灵机。 给出一个描述 并行计算结构和到该结构的输入， 评价者应该能够自我模拟。 短期计划 实现这一长期目标的主要途径是研究 算法，特别是集合和图论算法。 库 高效的数据/处理器结构，可用作建筑物 正在开发更复杂算法中的块。 研究 还研究了如何调试并行程序等 很容易理解。

The goal of this research program is to understand the limitations and capabilities of computing hardware. Discovery of new computing architectures and algorithms for those architectures is another aim, and mathematical proof is the methodology used. The work focuses on the issue of programming parallel computers. This study examines how parallel supercomputers based on fat-trees, a new class of general-purpose routing networks, might reasonably be programmed. The long-term goal is to build a "metacircular evaluator," which is like a Lisp interpreter or a universal Turing machine. Given a description of a parallel computing structure and inputs to the structure, the evaluator should be able to simulate itself. The short-term plan leading toward this long-term goal is to study specific parallel algorithms, particularly set- and graph-theoretic ones. A library of efficient data/processor structures which can be used as building blocks in more complicated algorithms is being developed. The research also investigates how parallel programs might be debugged and more easily understood.