Can any algorithm, never mind how abstract, be modeled by a generalized machine very closely and faithfully? ... If we stick to one abstract level (abstracting from low-level details and being oblivious to a possible higher-level picture) and if the states of the algorithm reflect all the pertinent information, then a particular small instruction set suffices in all cases.
adapted from Yuri Gurevich, "Sequential Abstract State Machines Capture Sequential Algorithms"
[an error occurred while processing this directive]
URL:
http://web.eecs.umich.edu/gasm/index.html (page only)
last update: Thursday, 08-Sep-2016 19:59:15 EDT