If folks would like to learn these ideas by hand via programming, i highly recommend Tom Stuart's Understanding Computation From Simple Machines to Impossible Programs - https://computationbook.com/
You might also like Algorithmics The Spirit of Computing by the great David Harel (https://en.wikipedia.org/wiki/David_Harel). The book is accessible to the intelligent general reader (though not a popular science book) and covers its domain rather comprehensively.
If folks would like to learn these ideas by hand via programming, i highly recommend Tom Stuart's Understanding Computation From Simple Machines to Impossible Programs - https://computationbook.com/