I cannot say I agree that the list of books provided by llamaz is good. The suggestions given so far are college-level CS textbooks (like SICP) and may be too difficult to start with for somebody without the necessary background knowledge. Unless your friend was already a college student in a CS program, I would recommend looking for books and instructional materials targeted at the high-school level instead.

Also bear in mind that without access to a computer or external tutelage, it's going to be very difficult for your friend to know whether or not his code is working properly. Stratoscope's suggestion of hand execution (https://news.ycombinator.com/item?id=12668865) is a good suggestion to help combat this issue. However, this means most likely that your friend will need to start with a language that's simple in structure; this disqualifies most modern languages. BASIC, Pascal, C or other extremely simple languages will be most amenable to this type of hand execution.

SICP is an introductory text, and is usually taught to first-year undergraduates. We don't even know what sort of educational background this friend has, but if he can do algebra, then he'll be able to do the exercises in the first chapter and check his answers. Furthermore, because Scheme uses the substitution model, doing the exercises on paper is possible. It'll take care and attention to detail, but every Scheme expression can be expanded and reduced according to simple rules, just like in algebra. The same cannot be said for most other languages.

SICP is perfect for studying without a computer. I've done it that way and it was a great experience. However, while it is presented as an introductory textbook, it moves fast. It depends on the learner.

Hmm. The pages move only as fast as you turn them :)

It's probably safe say that it's more concise than others that I have read. A sentence in SICP could become a paragraph in a lesser book.

Right. In a classroom with lots of bright students and lectures and Q&A it works great. With access to supplemental online resources also great. With none of that I think it would depend on the student and their patience, aptitude, and background.

Given that the person is in prison, it seems rather improbable that s/he was on a course to be a first-year undergraduate or is particularly familiar with algebra. The average person doesn't know algebra all that well, you know.

Frankly, I do not understand the people who are attempting to push CS textbooks on this person. The original question does not contain the words "computer science" anywhere within it.

SICP is entirely focused on the practical aspects of programming. There's nothing in there about the halting problem, or the Church-Turing thesis. The discussion of run-time and space requirements divides everything into constant time/space and everything else. That's useful for figuring out when your recursive procedure evolves a process that needs only constant stack space. There's no study of algorithms or data structures (well, there's simple lists and tagged data, but no b-trees, red-black trees, etc).

SICP might be a good programming book, but I'm not sure it's a good book. If your friend doesn't have programming experience something like "Code: The Hidden Language of Computer Hardware and Software" might be an easier way to start. Here is the first paragraph from each for comparison:

SICP: "We are about to study the idea of a computational process. Computational processes are abstract beings that inhabit computers. As they evolve, processes manipulate other abstract things called data. The evolution of a process is directed by a pattern of rules called a program. People create programs to direct processes. In effect, we conjure the spirits of the computer with our spells."

Code: "You're 10 years old. Your best friend lives across the street. In fact, the windows of your bedrooms face each other. Every night, after your parents have declared bedtime at the usual indecently early hour, you still need to exchange thoughts, observations, secrets, gossip, jokes, and dreams. No one can blame you. After all, the impulse to communicate is one of the most human of traits."

I don't think the prison superintendent will enjoy that last paragraph.