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