29 September 2023

On Machines XIV: Turing Machines

"For two things both to believe that snow is white, they need not to be physically similar in any specifiable way, but they must both be in a 'functional' condition or state specifiable in the most functional language; they must share a Turing machine description according to which they are both in some particular logical state (which is roughly like two different computers having the same program and being in the same "place" in the program). […] it is a type functionalism - each mental type is identifiable as a functional type in the language of Turing machine description." (Daniel Dennett,"Brainstorms", 1978)

"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)

"Unlike the Babbage-Boole machine, the Turing machine could in principle run all flexible programs, for it allowed the course of the calculation to be influenced by the running of the calculation itself." (Konrad Zuse, "The Computer - My Life" 1993)

"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." (John L Casti, "Mathematical Mountaintops: The Five Most Famous Problems of All Time", 2001)

"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)

"The Turing machine (which was hypothetical at the time) didn’t provide a universal algorithm for all mathematical problems; in fact, Turing proved that no such algorithm exists. However, it did help lay the foundation for how the modern computer would work. Most notably, Turing introduced the concept of a universal computing machine - a theoretical device capable of performing any logical operation that can be expressed algorithmically." (Robert Barton & Jerome Henry, "Demystifying Generative AI A Practical and Intuitive Introduction", 2026)

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...

🪸On Systems Thinking: On Function (1990-1999)

"An artificial neural network is an information-processing system that has certain performance characteristics in common with biologica...