archives

The Origins of the Turing Thesis Myth

The Origins of the Turing Thesis Myth
In this paper, we identify and analyze the historical reasons for the widespread acceptance of what we call the Turing Thesis myth, which extends the Turing Thesis to imply that Turing Machines model all computers.
The paper discusses how
Turing Thesis: Whenever there is an effective method (algorithm) for obtaining the values of a mathematical function, the function can be computed by a TM.
became
Strong Turing Thesis: A TM can do (compute) anything that a computer can do.
While certainly nothing new for LtU regulars, the paper still has some educational value.

[on edit: Warning, some of the statements in the paper may aggravate Haskell programmers]

By Andris Birkmanis at 2004-08-20 14:41 | LtU Forum | 15 comments | other blogs | 46879 reads

Introduction to computability logic

Introduction to computability logic (pre-print)
... The intuitive notion of (interactive) computational problems is formalized as a certain new, procedural-rule-free sort of games (called static games) between the machine and the environment, and computability is understood as existence of an interactive Turing machine that wins the game against any possible environment.
To all the lovers of games (and Turing machines :)

To claim relevance to PLT: computability logic can be seen as an alternative to linear logic (both being resource-aware). Also, interactive programming can be seen as a game between a programmer and PL environment...

Actually, I enjoyed the first part of the paper more (before getting to Turing machine).

By Andris Birkmanis at 2004-08-20 16:02 | LtU Forum | 21 comments | other blogs | 14107 reads