Дискретната математика бе един от най-забавните за мен предмети в университета. Не ми се отдаваше и не бе безкрайно полезна в работата ми, но пък разказваше за мистични неща като „крайни автомати“, „стекови автомати“ и „машини на Тюринг“. Шантави работи, последните от които имали мощността на който и да е език за програмиране. Не запомних много, но у мен остана усещане, че това е много интересна материя. От тогава все ми се искаше да се върна към нея. Тази книга ми даде възможност.

Understanding Computation разказва за изчислимост. Това е дял от компютърните науки, който разглежда различни модели за изпълнение (машини) и на какво са способни. Занимава се с ред забавни въпроси, като например дали една програма може да определи дали друга забива (не, не може). Примерите са на Ruby и за почти всичко обяснено има написан код, който го симулира.

Книгата започва с прост език за програмиране и няколко начина, по които може да бъде имплементиран. След това скача на всевъзможните изчислителни модели – крайни автомати, стекови автомати, машини на Тюринг и недетерминистичните им версии. Показва как регулярни изрази се изпълняват с крайни автомати, как езици могат да се разпознават с недетерминирани стекови автомати и как машина на Тюринг може да симулира друга машина на Тюринг. Показва ред забавни неща, включително един алгоритъм за минимизация на краен автомат, който ми се стори толкова невероятен, че трябваше да го пробвам, за да се уверя, че наистина работи.

След това, книгата разказва за ламдба смятане. Обяснява основните положения, показва Y комбинатора и дори имплементира FizzBuzz (наред с числа, масиви и низове) само с анонимни функции (като в тази презентация). Последното е впечатляващо – беше ми изключително трудно да си представя как може да се направи аритметика само с ламбди.

Всъщност, ламбда смятането не е единствения универсален модел. Има ред други, кой от кой по-шантав, които е трудно човек да повярва, че са равномощни с машина на Тюринг (и съответно който и да е език за програмиране). Няколко такива са разгледани и още ми е трудно да ги приема (например Rule 110 или йота комбинатора).

Ако имате интерес към любопитните аспекти на компютрите, тази книга ще ви хареса. Написана е на достъпен език – нямате нужда от „академични“ познания по компютърни науки. Ако сте учили това в университета, може да ви опресни паметта. Ако не сте – ще откриете цял нов свят.