I have a NAS which I am using to host a PSE catalog. Can this catalog be shared with another computer running PSE 13?
I can't answer for PSE, but Lightroom can open catalogues from other instances of lightroom just fine, and is actually one of the methods I use when traveling with my laptop.
A quick Google - search leads to this faq for older versions of PSE, and it states that as long as you have the photos and catalogue accessible from all PC's, it's possible to have it on an external drive.
TL/DR : Lightroom can do it just fine, earlier versions of PSE can do it, and PSE 13 should also be able to.