"A Universal Turing Machine is an ideal mathematical object; it represents a formal manipulation of symbols and owes allegiance to criteria of logical consistency but not to physical laws and constraints. Thus, for example, physical variables play no essential role in the concept of algorithm. In reality, however, every logical operation occurs at a minimum cost of KT of energy dissipation (where K is Boltzman's constant and T is temperature) and, in fact, occurs at a much higher cost to insure reliability." (Claudia Carello et al, "The Inadequacies of the Computer Metaphor", 1982)
"The Turing test is a popular approach, but it flies in the face of the standard scientific method which starts with the easier problems before facing the harder ones. Thus I soon raised the question with myself, 'What is the smallest or close to the smallest program I would believe could think?' Clearly if the program were divided into two parts then neither piece could think. I tried thinking about it each night as I put my head on the pillow to sleep, and after a year of considering the problem and getting nowhere I decided it was the wrong question! Perhaps 'thinking' is not a yes-no thing, but maybe it is a matter of degree." (Richard Hamming, "The Art of Doing Science and Engineering: Learning to Learn", 1997)
"A large part of Turing's genius was to show that the very primitive type of abstract computing machine he invented is actually the most general type of computer imaginable. In fact, every real-life computer that's ever been built is just a special case that materially embodies the machine that Turing dreamed up." (John L Casti, "Mathematical Mountaintops: The Five Most Famous Problems of All Time", 2001)
"[…] Turing machines are definitely not machines in the everyday sense of being material devices. Rather they are "paper computers," completely specified by their programs. Thus, when we use the term machine in what follows, the reader should read program or algorithm (i.e., software) and put all notions of hardware out of sight and out of mind." (John L Casti, "Mathematical Mountaintops: The Five Most Famous Problems of All Time", 2001)
"What's important about the Turing machine from a theoretical point of view is that it represents a formal mathematical object. So with the invention of the Turing machine, for the first time we had a well-defined notion of what it means to compute something."
"The subject of computational complexity theory is focused on classifying problems by how hard they are. […] (1) P problems are those that can be solved by a Turing machine (TM) (deterministic) in polynomial time. (‘P’ stands for polynomial). P problems form a class of problems that can be solved efficiently. (2) NP problems are those that can be solved by non-deterministic TM in polynomial time. A problem is in NP if you can quickly (in polynomial time) test whether a solution is correct (without worrying about how hard it might be to find the solution). NP problems are a class of problems that cannot be solved efficiently. NP does not stand for 'non-polynomial'. There are many complexity classes that are much harder than NP. (3) Undecidable problems: For some problems, we can prove that there is no algorithm that always solves them, no matter how much time or space is allowed." (K V N Sunitha & N Kalyani, "Formal Languages and Automata Theory", 2015)
No comments:
Post a Comment