> Would I place an in-text citation citing the book at the end of the paragraph?

Right after the paraphase. If it took a whole paragraph, so at the end of it.

> ... does every fact need to be cited? 

Generally, you do not need to cite information that is considered common knowledge. For instance, facts found in many sources or facts easily observed.

> if I were to say a PTM is a type of NTM, would this alone need to be cited with an in-text citation?

I would say no. Even [Wikipedia][1] is already aware of such. But be aware that it is an arbitrary choice. Expert audience will have different expectations of what constitutes common knowledge. If you have an adviser ask for his help.

Further, your argument might be stronger by using supporting evidence from other sources. Additional information related to the topic you're discussing would help to verify your claims. Hence, cite others work if such statement is crucial to your argumentation.

  [1]: https://en.wikipedia.org/wiki/Probabilistic_Turing_machine