In this post, we will see the book Algorithms and Automatic Computing Machines by B. A. Trakhtenbrot.
About the book
This booklet, Algorithms and Automatic Computing Machines, gives some of the historical aspects of algorithms and goes on to outline the development of the theory of algorithms that has taken place in the twentieth century. In defining the term algorithm, the author considers the close relation between algorithms and computing machines. The reader will need no specific mathematical background beyond intermediate algebra, but he should be able to follow a rather complex train of logical thought.
The author, B. A. TRAKHTENBROT, is Docent at the Penza Pedagogical Institute and has written several research papers in the field of mathematical logic.
The book was translated from Russian by was published in 1963 under the Topics in Mathematics series.
Credits to original uploader.
You can get the book here.
Follow us on The Internet Archive: https://archive.org/details/@mirtitles
Follow Us On Twitter: https://twitter.com/MirTitles
Write to us: mirtitles@gmail.com
Fork us at GitLab: https://gitlab.com/mirtitles/
Add new entries to the detailed book catalog here.
Contents
Introduction 1
CHAPTER 1. Numerical Algorithms 3
1. The Euclidean algorithm 3
2. Numerical algorithms 5
3. Diophantine equations 6
CHAPTER 2. Algorithms for Games 8
4. “Eleven matches” game 8
5. “Even wins” game 9
6. The tree of a game 10
7. Algorithm for a winning strategy 13
CHAPTER 3. An Algorithm for Finding Paths in a Labyrinth 17
8. Labyrinths 17
9. The labyrinth algorithm 19
10. Proof of the labyrinth algorithm 21
CHAPTER 4. The Word Problem 25
11. Associative calculi 25
12. The word equivalence problem 26
13. Word problems and labyrinths 28
14. Construction of algorithms 29
15. Automorphisms of a square 34
CHAPTER 5. Computing Machines with Automatic Control 38
16. Human computation 38
17. Computing machines 40
18. Machine instructions 42
CHAPTER 6. Programs (Machine Algorithms) 44
19. A program for linear equations 44
20. Iteration 46
21. The Euclidean algorithm 48
22. Operation of computing machines 50
23. Uses of computing machines 50
CHAPTER 7. The Need for a More Precise Definition of “Algorithm” 52
24. The existence of algorithms 52
25. The deducibility problem 54
26. Formulation of a definition of “algorithm” 57
CHAPTER 8. The Turing Machine 58
27. Definition of Turing machines 58
28. The operation of Turing machines 61
CHAPTER 9. The Realization of Algorithms in Turing Machines 65
29. Transforming n into n + 1 in decimal notation 65
30. Conversion into decimal notation 67
31. Addition 68
32. Repeated summation and multiplication 70
33. The Euclidean algorithm 71
34. Combinations of algorithms 74
CHAPTER 10. The Basic Hypothesis of the Theory of Algorithms 77
35. The basic hypothesis 77
36. Historical remarks 78
CHAPTER 11. The Universal Turing Machine 80
37. The imitation algorithm 80
38. The universal Turing machine 81
39. Coded groups of symbols 82
40. Algorithm for the universal Turing machine 83
CHAPTER 12. Algorithmically Unsolvable Problems 86
41. Church’s theorem 86
42. The self computability problem 86
43. Covering problems; the translatability problem 88
44. Historical remarks 89
CHAPTER 13. The Nonexistence of an Algorithm for the General Word Problem 92
45. Nonexistence of an algorithm for determining translatability 92 46. Unsolvability of the word equivalence problem 98
Concluding Remarks 100
Bibliography 101
Pingback: Algorithms and Automatic Computing Machines – Trakhtenbrot — Mir Books | Chet Aero Marine