Sachverhalt:
A.
Das Strafgericht des Kantons Basel-Stadt verurteilte X._ mit Entscheid vom 25. Juni 2015 wegen mehrfacher Vergehen gegen Art. 70 des Bundesgesetzes über die Invalidenversicherung (IVG; SR 831.20) in Verbindung mit Art. 87 Abs. 5 und 8 des Bundesgesetzes über die Alters- und Hinterlassenenversicherung (AHVG; SR 831.10) sowie Art. 31 Abs. 1 des Bundesgesetzes über den Allgemeinen Teil des Sozialversicherungsrechts (ATSG; SR 830.1) zu einer Geldstrafe von 120 Tagessätzen zu Fr. 20.--, stellte das Verfahren bezüglich der Handlungen vor dem 14. September 2000 infolge Verjährung ein und sprach ihn vom Vorwurf des gewerbsmässigen Betrugs frei. Die Schadenersatzforderung der IV-Stelle des Kantons Basel-Stadt wies es ab, soweit es darauf eintrat; auf jene der Pensionskasse Basel-Stadt trat es nicht ein.
Die Staatsanwaltschaft des Kantons Basel-Stadt erklärte Berufung mit dem Antrag, X._ sei wegen gewerbsmässigen Betrugs mit 30 Monaten Freiheitsstrafe bei einer Probezeit von zwei Jahren zu bestrafen, wovon 6 Monate unbedingt zu vollziehen seien. X._ liess Anschlussberufung erklären und Freispruch in allen Anklagepunkten beantragen. Die Pensionskasse Basel-Stadt erneuerte in ihrer Anschlussberufung ihre Schadenersatzforderung.
B.
Das Appellationsgericht Basel-Stadt bestätigte mit Entscheid vom 23. Juni 2016 die Verjährung bezüglich der vor dem 14. September 2000 vorgenommenen Handlungen sowie den Freispruch wegen gewerbsmässigen Betrugs und verurteilte X._ wegen mehrfacher Widerhandlung gegen das IVG zu einer Geldstrafe von 120 Tagessätzen zu Fr. 20.--. Die Schadenersatzforderung der Pensionskasse Basel-Stadt verwies es auf den "Sozialversicherungsweg".
C.
Die Staatsanwaltschaft führt Beschwerde in Strafsachen mit dem Antrag, es sei der vorinstanzliche Entscheid aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
D.
Das Appellationsgericht verzichtete auf eine Vernehmlassung und beantragte die Abweisung der Beschwerde. X._ liess auf Abweisung der Beschwerde schliessen, soweit darauf einzutreten sei, unter Kosten- und Entschädigungsfolge; eventualiter sei ihm die unentgeltliche Prozessführung und Verbeiständung zu bewilligen.

Erwägungen:
1.
Die Beschwerde muss ein Rechtsbegehren enthalten (<ref-law>). Da die Beschwerde an das Bundesgericht ein reformatorisches Rechtsmittel ist (<ref-law>), muss auch das Rechtsbegehren grundsätzlich reformatorisch gestellt werden; ein blosser Antrag auf Rückweisung ist nicht zulässig, ausser wenn das Bundesgericht ohnehin nicht reformatorisch entscheiden könnte (<ref-ruling> E. 1.2 S. 135; <ref-ruling> E. 1.3 S. 383 mit Hinweis). Da die Beschwerdebegründung zur Interpretation des Rechtsbegehrens beigezogen werden kann, genügt nach der Rechtsprechung des Bundesgerichts ein Begehren ohne einen Antrag in der Sache dann, wenn sich aus der Begründung zweifelsfrei ergibt, was mit der Beschwerde angestrebt wird (<ref-ruling> E. 1.3 S. 317; <ref-ruling> E. 1.2 S. 136; Urteil 6B_1168/2016 vom 17. März 2017 E. 1 mit Hinweisen).
Die Staatsanwaltschaft stellt keinen materiellen Antrag, sondern verlangt lediglich die Aufhebung des angefochtenen Urteils bezüglich des Freispruchs und der Strafe und Rückweisung an die Vorinstanz zur neuen Entscheidung. Dass das Bundesgericht im Falle der Gutheissung der Beschwerde nicht selbst in der Lage wäre, ein Sachurteil zu fällen, wird in der Beschwerdeschrift nicht geltend gemacht. Der Beschwerdebegründung lässt sich entnehmen, dass die Staatsanwaltschaft einen Schuldspruch wegen Betrugs erreichen möchte. Das Rechtsbegehren ist in diesem Sinne zu interpretieren. Die Beschwerde ist damit zulässig.
2.
2.1. Die Staatsanwaltschaft rügt eine Verletzung des Anklagegrundsatzes nach <ref-law>, da die Vorinstanz lediglich die in der Anklageschrift vom 9. Dezember 2014 explizit aufgeführten Unterlagen als massgebend für die Beurteilung des vorgeworfenen Betrugs erachtet habe, nicht aber die übrigen, sich bei den Untersuchungsakten befindenden ärztlichen Berichte und anderweitigen Unterlagen (vgl. II.C.1.a ihrer Beschwerde).
2.2. Der Anklagegrundsatz ergibt sich aus Art. 29 Abs. 2 und Art. 32 Abs. 2 BV sowie Art. 6 Ziff. 1 und 3 lit. a und b EMRK. Er ist zudem in <ref-law> verankert. Nach <ref-law> bezeichnet die Anklageschrift möglichst kurz, aber genau, die der beschuldigten Person vorgeworfenen Taten mit Beschreibung von Ort, Datum, Zeit, Art und Folgen der Tatausführung. Damit die Anklageschrift ihre doppelte Funktion der Umgrenzung und Information wahrnehmen kann, hat sie die der beschuldigten Person zur Last gelegten Delikte in ihrem Sachverhalt so präzise zu umschreiben, dass die Vorwürfe genügend konkretisiert sind (vgl. <ref-ruling> E. 6.2 und 6.3; <ref-ruling> E. 2a; je mit Hinweisen).
2.3. Gemäss Anklageschrift vom 9. Dezember 2014 wird dem Beschwerdegegner vorgeworfen, er habe im Nachgang zum Unfall vom 31. August 1996 mindestens vom 26. August 2000 bis zum Dezember 2010 Leistungen der Invalidenversicherung, der Schweizerischen Unfallversicherungsanstalt (Suva) und der Pensionskasse Basel-Stadt im Umfang von rund Fr. 898'300.-- erhalten, obwohl die notwendigen Voraussetzungen nicht erfüllt gewesen seien. Bezüglich des Vorwurfs des Betrugs zu Lasten der Invalidenversicherung wird ausgeführt, er habe in der Absicht, sich unrechtmässig zu bereichern, die Sozialversicherer über den tatsächlichen Umfang seiner Erwerbsunfähigkeit getäuscht, indem er trotz Meldepflicht Veränderungen seines Gesundheitszustandes nicht gemeldet und damit diese in ihrer nicht den tatsächlichen Begebenheiten entsprechenden Meinung bestärkt habe. Darüber hinaus habe er auch aktiv getäuscht, indem er wahrheitswidrige Angaben gemacht habe. Tatsächlich sei er in der Lage gewesen, als Gitarrist, Sänger und Manager der Band "A._" jährliche Einnahmen von mindestens Fr. 37'900.-- zu erzielen. Diese Tätigkeit habe er aber gegenüber den ihn untersuchenden Medizinalpersonen und den Angestellten der involvierten Sozialversicherungen verschwiegen, um seine Erwerbsfähigkeit geringer darzustellen, als sie gewesen sei. Dabei habe er ausgenutzt, dass bei Schmerzleiden wie Kopfschmerzen die objektiven Befunde limitiert seien und deshalb auf die subjektiven Angaben des Patienten abgestellt werden müsse, welche nur mit besonderer Mühe überprüfbar seien. Bezüglich des vorgeworfenen Betrugs zu Lasten der Unfallversicherung enthält die Anklageschrift eine Liste der vom Beschwerdegegner geschilderten Beschwerden, welche die involvierten Personen dazu veranlasst hätten, von einer zu hohen Einschränkung auszugehen, sowie eine Aufzählung von Tätigkeiten, welche der Beschwerdegegner nach eigenen Angaben nicht mehr ausüben könne, was jedoch nicht zutreffend sei. Beim Vorwurf des Betrugs zu Lasten der Pensionskasse hält die Anklageschrift fest, gestützt auf die Untersuchung des Beschwerdegegners durch den Leiter des Ärztlichen Dienstes und den Bericht des vertrauensärztlichen Dienstes sowie dem vom Beschwerdegegner unterzeichneten Antrag auf Vollpensionierung habe die Pensionskasse die Rente am 13. Oktober 2004 festgesetzt. Tatsächlich sei der Beschwerdegegner aber in der Lage gewesen, die bei den Ausführungen zur Invalidenversicherung dargelegten Tätigkeiten auszuüben. Dies habe er gegenüber den ihn untersuchenden Medizinalpersonen und den Angestellten der involvierten Sozialversicherung verschwiegen, um seine Erwerbsfähigkeit geringer darzustellen, als sie tatsächlich gewesen sei. Dabei habe er ausgenutzt, dass bei Schmerzleiden wie Kopfschmerzen die objektiven Befunde limitiert seien und deshalb auf die subjektiven Angaben des Patienten abgestellt werden müsse, welche nur mit besonderer Mühe überprüfbar seien.
2.4. Damit wird der Betrugsvorwurf ausreichend präzise umschrieben. Der Beschwerdegegner wusste, was ihm vorgeworfen wird. Nicht verlangt werden kann, dass sich bereits die Anklageschrift im Detail zu den einzelnen Gesprächen mit den Ärzten und Sachbearbeitern äussert, diese namentlich nennt sowie sämtliche in Frage kommenden Berichte und Protokolle aufführt (Urteil 6B_646/2012 vom 12. April 2013 E. 1.4). Somit erweist sich das Vorgehen der Vorinstanz als bundesrechtswidrig, indem sie den Vorwurf des gewerbsmässigen Betrugs lediglich unter Beachtung der in der Anklageschrift erwähnten ärztlichen Berichte, Fragebogen und Sachbearbeiterprotokolle prüfte, ihrer Beurteilung aber nicht die übrigen in den Untersuchungsakten sich befindenden sachdienlichen Unterlagen zugrunde legte. Dies stellt eine unzulässige Einschränkung ihrer Befugnisse dar. Vielmehr sind bei der Beurteilung des Betrugsvorwurfs sämtliche bei den Akten sich befindenden Anhaltspunkte zu berücksichtigen und zu würdigen. Der vorinstanzliche Entscheid ist aufzuheben und die Sache zu neuer Beurteilung an das kantonale Gericht zurückzuweisen.
3.
3.1. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser ist offensichtlich unrichtig oder beruht auf einer Rechtsverletzung im Sinne von <ref-law> (vgl. Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG). Wird vor Bundesgericht eine mangelhafte Sachverhaltsfeststellung gerügt, welche auf einer Rechtsverletzung im Sinne von <ref-law> beruht, geht es typischerweise um die Verletzung von Verfahrensvorschriften (Markus Schott, Basler Kommentar, Bundesgerichtsgesetz, 2. Aufl. 2011, N. 17 zu <ref-law>). Eine solche Rechtsverletzung ist etwa gegeben, wenn der vorinstanzliche Richter sich unter Verletzung von <ref-law> durch ein Geständnis gebunden fühlt (BERNARD CORBOZ, in: Commentaire de la LTF, 2. Aufl. 2014, N. 33 zu <ref-law>) Die Rechtsverletzung kann aber auch in einem unvollständig erstellten Sachverhalt liegen (Botschaft des Bundesrates vom 28. Februar 2001 zur Totalrevision der Bundesrechtspflege, BBl 2001 4202, 4338; <ref-ruling> E. 1.6; <ref-ruling> E. 3.7). Ermessensmissbrauch, -überschreitung und -unterschreitung sind Rechtsverletzungen und damit zulässige Beschwerdegründe nach <ref-law> (Schott, a.a.O., N. 34 zu <ref-law>).
3.2. Die Staatsanwaltschaft macht eine Ermessensüberschreitung der Vorinstanz im Rahmen der Beweiswürdigung nach <ref-law> geltend (vgl. II.C.1.b ihrer Beschwerde). Denn die Vorinstanz habe unter Ausserachtlassung verschiedener massgeblicher medizinischer Beurteilungen gestützt auf ihre eigene Einschätzung festgestellt, die Musikertätigkeit des Beschwerdegegners lasse weder auf eine Dienstfähigkeit im angestammten Beruf noch auf eine allgemeine Arbeitsfähigkeit schliessen. Zumindest hätte die Vorinstanz bei einem Abweichen von den Ansichten der sachverständigen Personen dies stichhaltig begründen müssen.
3.3.
3.3.1. Entgegen der Ansicht des Beschwerdegegners erfüllt die Beschwerdeschrift der Staatsanwaltschaft die Anforderungen der Rügepflicht. Denn vorliegend wird von der Staatsanwaltschaft nicht eine offensichtlich unrichtige und somit willkürliche Sachverhaltsfeststellung gerügt, sondern sie macht eine auf einer Ermessensüberschreitung und damit einer Rechtsverletzung beruhenden Sachverhaltsfeststellung geltend. Sie nennt explizit die durch die Vorinstanz als verletzt erachtete Verfahrensnorm (<ref-law>) und legt rechtsgenüglich dar, weshalb ihrer Ansicht nach das Vorgehen der Vorinstanz eine Ermessensüberschreitung und damit einen vor Bundesgericht zulässigen Beschwerdegrund darstellen soll. Zu prüfen ist nach dem Gesagten nicht eine willkürliche Beweiswürdigung, sondern ob der Vorinstanz durch die gerügte Nichtbeachtung der ärztlichen Berichte bei der Sachverhaltsermittlung eine Ermessensüberschreitung anzulasten ist.
3.3.2. Bei der Beurteilung des gewerbsmässigen Betrugs zum Nachteil der Sozialversicherungen geht es in der Regel nicht darum, ob die beschuldigte Person zu Unrecht Leistungen bezogen hat, sondern vielmehr darum, ob ein unrechtmässiger Leistungsbezug auf ein täuschendes Verhalten der beschuldigten Person zurückzuführen ist. Um dies beurteilen zu können, muss im Rahmen des Untersuchungs- und Strafverfahrens erstellt sein, dass die ärztlichen Experten in Kenntnis der zum Vorwurf des Betrugs führenden Umstände keine oder eine geringere leistungsbegründende Arbeitsunfähigkeit attestieren.
3.3.3. Zur Feststellung der zumutbaren Arbeitsfähigkeit im Rahmen der Sozialversicherungen ist es Aufgabe der Ärzte, den Gesundheitszustand zu beurteilen und dazu Stellung zu nehmen, in welchem Umfang und bezüglich welcher Tätigkeiten die versicherte Person arbeitsunfähig ist (<ref-ruling> E. 4; präzisiert mit <ref-ruling> E. 3.2). Hinsichtlich des Beweiswertes eines ärztlichen Berichts ist entscheidend, ob er für die streitigen Belange umfassend ist, auf allseitigen Untersuchungen beruht, auch die geklagten Beschwerden berücksichtigt, in Kenntnis der Vorakten (Anamnese) abgegeben worden ist, in der Beurteilung der medizinischen Zusammenhänge und Situation einleuchtet und ob die Schlussfolgerungen des Experten begründet sind; ausschlaggebend ist somit grundsätzlich weder die Herkunft des Beweismittels noch die Bezeichnung der eingereichten oder in Auftrag gegebenen Stellungnahme als Bericht oder Gutachten (<ref-ruling> E. 5.1; <ref-ruling> E. 3a). Dennoch hat es die Rechtsprechung mit dem Grundsatz der freien Beweiswürdigung als vereinbar erachtet, in Bezug auf bestimmte Formen medizinischer Berichte und Gutachten Richtlinien für die Beweiswürdigung aufzustellen. So darf etwa in Bezug auf Berichte von Hausärzten und behandelnden Fachärzten der Erfahrungstatsache Rechnung getragen werden, dass diese mitunter im Hinblick auf ihre auftragsrechtliche Vertrauensstellung im Zweifelsfall eher zugunsten ihrer Patienten aussagen (BGE <ref-ruling> E. 3b/cc; vgl. auch SVR 2014 IV Nr. 39 S. 137 E. 3.3.3, 9C_121/2014, und Urteil 8C_712/2008 vom 5. Februar 2009 E. 3.2). In diesem Zusammenhang ist auch auf den Unterschied zwischen Behandlungs- und Begutachtungsauftrag hinzuweisen (SVR 2008 IV Nr. 15 S. 43 E. 2.2.1, I 514/06). Bei vom Gericht eingeholten Gutachten gilt der Grundsatz, dass das Gericht "nicht ohne zwingende Gründe" vom Gutachten abweicht, wohingegen den von der Verwaltung bei versicherungsexternen Fachärzten in Auftrag gegebenen Gutachten solange voller Beweiswert zukommt, als nicht konkrete Indizien gegen ihre Zuverlässigkeit sprechen (<ref-ruling> E. 4.4). Die für das Sozialversicherungsrecht aufgestellten Beweisanforderungen in medizinischer Hinsicht gelten auch bei der Beurteilung eines (gewerbsmässigen) Betrugs infolge unrechtmässigen Bezugs von Sozialversicherungsleistungen (Urteil 6B_646/2012 vom 12. April 2013 E. 2.4.2 und 2.5.1).
3.4. Die Vorinstanz hat ohne Abstützung auf eine ärztliche Einschätzung festgestellt, die Musikertätigkeit des Beschwerdegegners vermöge keine Dienstfähigkeit im angestammten Beruf und keine allgemeine Arbeitsfähigkeit zu begründen. Dieses Vorgehen verletzt nicht nur die bundesgerichtlichen Vorgaben zur Beurteilung der zumutbaren Arbeitsfähigkeit resp. zur Beweiswürdigung von ärztlichen Berichten, sondern stellt auch eine Ermessensüberschreitung der Vorinstanz dar, indem sie ihr nicht fachspezifisches Wissen anstelle der Expertenmeinung setzte. Namentlich das polydisziplinäre Gutachten des Zentrums für Medizinische Begutachtung, Basel, vom 23. April 2013, welchem - sofern es den Anforderungen von <ref-ruling> E. 5.1 entspricht - nach den Grundsätzen der Rechtsprechung massgebliches Gewicht zur Beantwortung dieser Frage zukommt, hätte beigezogen werden müssen; zumindest hätte die Vorinstanz darlegen müssen, weshalb dieses nicht aussagekräftig für die Frage der zumutbaren Arbeitsfähigkeit sein soll. Die Beschwerde erweist sich auch in diesem Punkt als begründet.
4.
Die Staatsanwaltschaft rügt weiter eine bundesrechtswidrige Verneinung verschiedener Tatbestandselemente des Betrugs nach <ref-law> durch die Vorinstanz. Schliesslich beanstandet sie eine unrichtige Sachverhaltsfeststellung nach <ref-law>, indem die Vorinstanz aktenwidrig fehlende Anzeichen für falsche Angaben des Beschwerdegegners gegenüber den Ärzten verneine, die Initiative zur Frühberentung des Beschwerdegegners dem Amtsarzt zuschreibe und sich auf den Standpunkt gestellt habe, die Auftritte des Beschwerdegegners liessen weder auf eine Dienst- noch auf eine allgemeine Arbeitsfähigkeit schliessen.
Wie es sich damit verhält, kann offenblieben. Denn die Sache ist bereits aus anderen Gründen unter Aufhebung des Entscheids vom 23. Juni 2016 an die Vorinstanz zur Feststellung des massgebenden Sachverhalts unter Zugrundelegung der gesamten Untersuchungsakten und zu neuer Beurteilung zurückzuweisen. Dabei wird das kantonale Gericht zu berücksichtigen haben, dass nach der Rechtsprechung die unterlassene Meldung eines verbesserten Gesundheitszustandes mangels Garantenstellung keinen Betrug im Sinne von <ref-law> darstellt, dass aber in Fällen, in welchen die leistungsbeziehende Person auf Nachfragen der (Sozial-) Versicherer nicht wahrheitsgemäss antwortet oder ihre verbesserten Verhältnisse nicht offen legt, eine aktive Täuschung vorliegt (<ref-ruling> E. 2.4.6; vgl. zur Tathandlung der arglistigen Täuschung nach <ref-law> im Rahmen des Sozialversicherungsbetrugs auch Urteil 6B_188/2007 vom 15. August 2007 E. 6.4, Urteil 6B_125/2012 vom 28. Juni 2012 E. 5.3, Urteil 6B_531/2012 vom 23. April 2013 E. 3.3 und 3.4, Urteil 6B_1029/2013 vom 24. Februar 2014 E. 1.4 und Urteil 6B_1168/2016 vom 17. März 2017 E. 3.3 und 3.4).
5.
Die Beschwerde wird gutgeheissen. Der obsiegenden Staatsanwaltschaft ist keine Entschädigung auszurichten (<ref-law>). Dem Beschwerdegegner wären die Gerichtskosten als unterliegende Partei grundsätzlich aufzuerlegen (<ref-law>). Er hat indessen um unentgeltliche Rechtspflege und Verbeiständung ersucht. Das Gesuch ist gutzuheissen, da seine Bedürftigkeit erstellt ist und die Anträge angesichts seiner prozessualen Stellung als Beschwerdegegner nicht als aussichtslos bezeichnet werden können (<ref-law>; vgl. auch Urteil 8C_743/2010 vom 24. März 2011 E. 5.2 sowie Thomas Geiser, Basler Kommentar, Bundesgerichtsgesetz, 2. Aufl. 2011, N. 22 zu <ref-law>). Damit sind keine Kosten zu erheben und ist der Rechtsvertreter des Beschwerdegegners aus der Bundesgerichtskasse zu entschädigen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist. Das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 23. Juni 2016 wird aufgehoben und die Sache an das Appellationsgericht des Kantons Basel-Stadt zu neuem Entscheid zurückgewiesen.
2.
Das Gesuch um unentgeltliche Rechtspflege wird gutgeheissen. Dem Beschwerdegegner wird Rechtsanwalt Nicolas Roulet als unentgeltlicher Rechtsbeistand beigegeben.
3.
Es werden keine Gerichtskosten erhoben.
4.
Der Rechtsvertreter des Beschwerdegegners, Rechtsanwalt Nicolas Roulet, wird aus der Bundesgerichtskasse mit Fr. 1'500.- entschädigt.
5.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 1. September 2017
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Riedi Hunold