Church's Thesis asserts that the only numeric functions that can be calculated by effective means are the recursive ones, which are the same, extensionally, as the Turing-computable numeric functions. The Abstract State Machine Theorem states that every classical algorithm is behaviorally equivalent to an abstract state machine. This theorem presupposes three natural postulates about algorithmic computation. Here, we show that augmenting those postulates with an additional requirement regarding basic operations gives a natural axiomatization of computability and a proof of Church's (...) Thesis, as Gödel and others suggested may be possible. In a similar way, but with a different set of basic operations, one can prove Turing's Thesis, characterizing the effective string functions, and--in particular--the effectively-computable functions on string representations of numbers. (shrink)

People usually regard algorithms as more abstract than the programs that implement them. The natural way to formalize this idea is that algorithms are equivalence classes of programs with respect to a suitable equivalence relation. We argue that no such equivalence relation exists.

This festschrift volume is dedicated to Boris (Boaz) Trakhtenbrot on the occasion of his 85th birthday. For over half a century, Trakhtenbrot has been making seminal contributions to virtually all of the central areas of theoretical computer science. He is universally admired as a founding father and long-standing pillar of the discipline of computer science. On Friday, 28 April 2006, the School of Computer Science at Tel Aviv University held a “Computation Day Celebrating Boaz (Boris) Trakhtenbrot's Eighty-Fifth Birthday”. As a (...) follow-up to that event, his students and colleagues were asked to contribute to a volume in his honor and in recognition of his grand contributions to the field. The book opens with two historical overviews and a bibliography. These are followed by 33 thoroughly reviewed technical contributions. The broad range of topics covered include mathematical logic, logics for computer science, mathematics for computer science, automata and formal languages, asynchronous computation, semantics of programming languages, verification, and software engineering. This tapestry of subjects stands as testimony to the vast scope of Trakhtenbrot's achievements and the profound influence he has had on the field. (shrink)