Sachverhalt: A. Die A._ AG hat Sitz in U._/ZH. Statutengemäss bezweckt sie den Betrieb eines histopathologischen, das heisst auf die Feststellung von Erkrankungen des menschlichen Gewebes ausgerichteten Diagnosezentrums. Sie verfügt über eine Bewilligung des Kantons Zürich zum Betrieb einer ambulanten ärztlichen Institution. Ihre Klientschaft setzt sich aus inländischen Spitälern und Ärzten zusammen. Gewisse Untersuchungen führt sie nicht selbst durch, insbesondere bezieht sie Laboratoriumsleistungen auch aus dem Ausland, so aus der Tschechischen Republik und der Bundesrepublik Deutschland. Die A._ AG und die beiden ausländischen Laboratorien sind in dem von der Eidgenössischen Steuerverwaltung (ESTV) geführten Register der Mehrwertsteuerpflichtigen nicht verzeichnet. B. Mit Schreiben vom 15. April 2013 erkundigte die A._ AG sich bei der ESTV danach, ob ihre im Jahr 2012 aus dem Ausland bezogenen humanmedizinischen Laboratoriumsleistungen im Gesamtumfang von mehr als Fr. 10'000.-- der Bezugsteuer unterlägen. Sie vertrat dabei die Auffassung, eine (von vornherein auf den Bezug beschränkte) Steuerpflicht sei nicht gegeben, weil es sich bei den Leistungen um Heilbehandlungen handle, was zum Erbringerortprinzip führe (Art. 8 Abs. 2 lit. a MWSTG). Der Ort der Leistung liege mithin im Ausland. Entsprechend löse der Vorgang keine Bezugsteuer im Sinne von Art. 45 MWSTG aus. Selbst wenn das Empfängerortprinzip zum Tragen käme (Art. 8 Abs. 1 MWSTG), sei keine Bezugsteuerpflicht gegeben, da es sich um von der Steuer ausgenommene Leistungen handle (Art. 21 Abs. 2 MWSTG). C. Die ESTV beantwortete die Anfrage am 13. Juni 2013 dahingehend, dass die Voraussetzungen der Bezugsteuer vorlägen. Gemäss Ziff. 9.2 der MWST-Branchen-Info 21 ("Gesundheitswesen") seien nur Leistungen solcher Institutionen von der Besteuerung ausgenommen, die über eine kantonale Bewilligung zum Betrieb eines medizinischen Laboratoriums verfügten. Weil die im Ausland ansässigen Laboratorien keine kantonale Bewilligung vorweisen könnten, fehle eine von der Steuer ausgenommene Heilbehandlung. Der Ort der Leistung richte sich nach dem Empfängerortprinzip, was die Bezugsteuer auslöse. D. Mit Blick darauf reichte die A._ AG eine Aufstellung der in den Jahren 2011 und 2012 aus dem Ausland erlangten Laboratoriumsleistungen nach. Demzufolge hatte sie in den beiden Jahren Leistungen von Fr. 67'296.77 bzw. Fr. 94'946.91 bezogen. Mit Ergänzungsabrechnungen vom 8. Oktober 2013 belastete die ESTV die Bezugsteuer nach; diese belief sich auf Fr. 5'383.74 bzw. Fr. 7'595.75. Die A._ AG bestritt dies am 6. März 2014 und gab überdies bekannt, sie habe im Jahr 2013 gleichartige Leistungen von Fr. 90'866.10 bezogen. Dies veranlasste die ESTV am 17. März 2014 zu einer weiteren Ergänzungsabrechnung, diesmal über Fr. 7'255.05. Mit Verfügung vom 6. Mai 2014 hielt die ESTV an ihrer Sichtweise fest und bestätigte sie die Ergänzungsabrechnungen vom 8. Oktober 2013 bzw. 17. März 2014. Im Einspracheentscheid vom 16. April 2015 bekräftigte die ESTV ihren Standpunkt. Obwohl im Gesetz nicht ausdrücklich erwähnt, sei auch von ausländischen Laboratorien eine kantonale Bewilligung zu verlangen, damit diese eine von der Steuer ausgenommene Leistungen erbringen könnten. E. Dagegen gelangte die A._ AG an das Bundesverwaltungsgericht. Mit Urteil A-3112/2015 vom 22. Oktober 2016 hiess dieses die Beschwerde gut und wies es die Sache zur Fällung eines neuen Entscheides im Sinne der Erwägungen an die ESTV zurück. Das Bundesverwaltungsgericht kam im Wesentlichen zum Schluss, im Fall ausländischer Zentren für Diagnostik sei eine kantonale Bewilligung zum Betrieb einer ambulanten ärztlichen Institution von vornherein entbehrlich. Ein ausländisches Laboratorium qualifiziere als "Zentrum für Diagnostik" im mehrwertsteuerlichen Sinn, falls es Leistungen erbringe, die gemäss Vermerk in der Analysenliste auch im Ausland kassenpflichtig durchgeführt werden können (E. 5.3). Von einer "Heilbehandlung" oder einer "damit eng verbundenen Leistung" sei in einem solchen Fall ebenfalls nur bei Leistungen zu sprechen, die gemäss Vermerk in der Analysenliste auch im Ausland kassenpflichtig durchgeführt werden können. Treffe dies zu, könne das ausländische Laboratorium steuerausgenommene Leistungen ins Inland erbringen (E. 5.4). Die ESTV habe zum Charakter der vom deutschen und tschechischen Laboratorium erbrachten Leistungen keine Feststellungen getroffen. Da dies aber unumgänglich sei, sei die Sache an die ESTV zurückzuweisen. F. Mit Eingabe vom 30. November 2015 erhebt die ESTV beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten. Sie beantragt die Aufhebung des vorinstanzlichen Urteils sowie die Bestätigung des Einspracheentscheides vom 16. April 2015. Eventualiter sei die auszurichtende Parteientschädigung aufgrund der Akten zu bestimmen und auf höchstens Fr. 3'000.-- festzusetzen. Die A._ AG sieht von einer Beschwerde ab und beschränkt sich auf eine Vernehmlassung. Darin beantragt sie erstens, die Ziff. 1 des Dispositivs des angefochtenen Entscheids sei insoweit aufzuheben, als die Sache im Sinne der Erwägungen an die Vorinstanz zurückgewiesen wird. Aufzuheben sei zweitens auch der Einspracheentscheid der ESTV vom 16. April 2015. Drittens sei festzustellen, dass sie, die A._ AG, die im Einspracheentscheid verfügten Mehrwertsteuern je zuzüglich Zins nicht schulde und ihr die unter Vorbehalt geleisteten Zahlungen zuzüglich Zins zurückzuerstatten bzw. gutzuschreiben seien. Viertens sei die Ziff. 3 des Dispositivs bezüglich der Parteientschädigung zu bestätigen und der Eventualantrag der ESTV abzuweisen. Die Vorinstanz verzichtet auf eine Stellungnahme. Das Bundesgericht hat die Angelegenheit am 9. Dezember 2016 öffentlich beraten.