首页 | 本学科首页   官方微博 | 高级检索  
     


Simulating Turing machines on Maurer machines
Authors:J.A. Bergstra  C.A. Middelburg  
Affiliation:aProgramming Research Group, University of Amsterdam, P.O. Box 41882, 1009 DB Amsterdam, Netherlands;bDepartment of Philosophy, Utrecht University, P.O. Box 80126, 3508 TC Utrecht, Netherlands
Abstract:In a previous paper, we used Maurer machines to model and analyse micro-architectures. In the current paper, we investigate the connections between Turing machines and Maurer machines with the purpose to gain an insight into computability issues relating to Maurer machines. We introduce ways to simulate Turing machines on a Maurer machine which, dissenting from the classical theory of computability, take into account that in reality computations always take place on finite machines. In one of those ways, multi-threads and thread forking have an interesting theoretical application.
Keywords:Turing machine   Maurer machine   Thread algebra   Strategic interleaving   Thread forking   Fair interleaving strategy
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号