There is mind-blowing paper, that gives exhaustive anwser to this question: https://hal.inria.fr/hal-01519828/document
This paper is about chemical reaction networks, but in 2010 it was shown, that any chemical reaction network is realizable in DNA: https://www.pnas.org/content/pnas/107/12/5393.full.pdf
2) Yes, it was figured out in 2006, how to do logic gates in DNA: https://science.sciencemag.org/content/314/5805/1585