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