Sachverhalt:
A.
Am 22. Dezember 2014 erhob die Staatsanwaltschaft Basel-Stadt gegen X._ Anklage wegen teilweise versuchten, gewerbsmässigen Betrugs sowie wegen Betrugs, eventualiter wegen Widerhandlung gegen das Bundesgesetz über die Invalidenversicherung (IVG; SR 831.20) sowie gegen das Bundesgesetz über die Ergänzungsleistungen zur Alters-, Hinterlassenen- und Invalidenversicherung (ELG; SR 831.30).
B.
Das Strafgericht des Kantons Basel-Stadt sprach X._ am 26. August 2015 der Widerhandlung gegen das IVG und gegen das ELG schuldig. Es verurteilte ihn zu einer bedingten Geldstrafe von 180 Tagessätzen zu Fr. 30.--. Von der Anklage des teilweise versuchten, gewerbsmässigen Betrugs sowie des Betrugs wurde X._ freigesprochen. Gegen das Urteil legte die Staatsanwaltschaft Berufung ein.
C.
Das Appellationsgericht des Kantons Basel-Stadt sprach X._ mit Urteil vom 13. Mai 2016 des teilweise versuchten, gewerbsmässigen Betrugs sowie des mehrfachen Betrugs schuldig und verurteilte ihn zu einer bedingten Freiheitsstrafe von 18 Monaten.
D.
Mit Beschwerde in Strafsachen beantragt X._, das Urteil des Appellationsgerichts sei bezüglich des Schuldspruchs und der Strafe aufzuheben, die Sache sei zur neuen Entscheidung an das Appellationsgericht zurückzuweisen und es sei ihm für das bundesgerichtliche Verfahren die unentgeltliche Rechtspflege und Verbeiständung zu gewähren.
E.
Das Appellationsgericht verzichtet auf eine Vernehmlassung und beantragt die Abweisung der Beschwerde. Die Staatsanwaltschaft stellt ebenfalls Antrag auf Beschwerdeabweisung.

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; Urteile 6B_938/2014 vom 18. Februar 2015 E. 1 und 6B_515/2014 vom 26. August 2014 E. 2.1; je mit Hinweisen).
Der Beschwerdeführer stellt keinen materiellen Antrag, sondern verlangt lediglich die Aufhebung des angefochtenen Urteils bezüglich des Schuldspruchs 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 der Beschwerdeführer einen Freispruch vom Vorwurf des Betrugs erreichen möchte. Das Rechtsbegehren ist in diesem Sinne zu interpretieren. Die Beschwerde ist damit zulässig.
2.
Der Beschwerdeführer rügt, die Vorinstanz habe den Sachverhalt offensichtlich unrichtig festgestellt und somit Bundesrecht verletzt.
2.1. Hintergrund des Strafverfahrens bildet der Vorwurf, der Beschwerdeführer habe zwischen dem 29. April 2005 und dem 31. Dezember 2010 von der Versicherung A._ AG, der Invalidenversicherung und dem Amt für Sozialbeiträge Basel-Stadt zu Unrecht Leistungen bezogen und zu beziehen versucht. Die Vorinstanz hält in sachverhaltsmässiger Hinsicht fest, der Beschwerdeführer habe gegenüber den Ärzten über seinen Gesundheitszustand falsche Angaben gemacht, indem er vorgegeben habe, es gehe ihm sehr schlecht (er sei meist zu Hause und weitgehend inaktiv) und er könne nicht als Taxichauffeur arbeiten. Dies habe zur Attestierung seiner vollen bzw. teilweisen Arbeitsunfähigkeit geführt. Sodann habe er gegenüber der A._ AG am 19. September 2005 schriftlich erklärt, dass "er einfach gar nichts mache" und nur ein wenig spazieren gehe. Anlässlich der Besprechung bei der A._ AG vom 1. Juli 2009 habe der Beschwerdeführer angegeben, er leide unter Müdigkeit, Kraftlosigkeit, Kopfschmerzen, Konzentrationsstörungen und habe keine Energie. Sogar der Fussweg von hundert Metern zur Besprechung sei für ihn "sehr weit, mühsam und beschwerlich" gewesen. Diesen Angaben des Beschwerdeführers stehen gemäss der Sachverhaltsfeststellung der Vorinstanz diverse Indizien und Beweise dafür gegenüber, dass er im inkriminierten Zeitraum regelmässig als Taxischauffeur gearbeitet hat. Sein Taxibetrieb, die "B._ GmbH" sei erst mit Beschluss des Zivilgerichts vom 27. Juli 2010 aufgelöst worden. In den Jahren 2006 und 2007 sei er viermal wegen Übertretungen gegen das Taxigesetz gebüsst worden. Seine Fahrfähigkeit habe sich der Beschwerdeführer am 17. Februar 2009 amtlich bestätigen lassen. Bei der Durchsuchung seines Fahrzeuges seien Utensilien vorgefunden worden, welche auf die Benutzung des Wagens als Taxi hinwiesen. Der Fahrzeugprüfbericht für die Zeitspanne vom 3. Oktober 2006 bis zum 3. Oktober 2007 belege eine Streckenbewältigung des auf den Beschwerdeführer zugelassenen Fahrzeuges von bis zu 37'767 km. Aus der von der A._ AG in Auftrag gegebenen Observierung gehe hervor, dass der Beschwerdeführer in der Nacht vom 25. auf den 26. April 2009 mindestens vier Stunden, am 2. Mai 2009 mindestens dreieinhalb Stunden und am 3. Mai 2009 fast sechs Stunden am Stück als Taxichauffeur gearbeitet habe. Gemäss der Aussage seines Schwiegersohns habe der Beschwerdeführer zwischen 2006 und 2009 als Taxifahrer gearbeitet, und zwar 30 bis 40 Stunden pro Woche. Er habe den Beschwerdeführer auch an jeder Messe als Taxichauffeur gesehen. Weiter hält die Vorinstanz fest, aus den Aussagen des Beschwerdeführers selbst, wonach er zwischen Sommer 2008 und Anfang 2011 "mehr als 14-mal" nach Frankfurt gefahren sei und er im Jahr 2009 "x-mal" seine damalige Freundin in Deutschland besucht habe, gehe hervor, dass der Beschwerdeführer in der Lage war, Autofahrten von drei bis vier Stunden zurückzulegen. Der von der IV-Stelle Basel-Stadt mit der Erstellung eines Gutachtens beauftragte Dr. med. C._ gehe in seinem Gutachten vom 2. Februar 2013 von einer Arbeitsunfähigkeit des Beschwerdeführers von 40 % aus.
2.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die vorinstanzliche Sachverhaltsfeststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; vgl. auch <ref-law>). Offensichtlich unrichtig im Sinne von <ref-law> ist die Sachverhaltsfeststellung, wenn sie willkürlich ist (<ref-ruling> E. 1.3.1 S. 253 mit Hinweis; vgl. zum Begriff der Willkür: <ref-ruling> E. 1.2 S. 308 f.; <ref-ruling> E. 2.1 S. 18 f.; je mit Hinweisen).
Dem Grundsatz "in dubio pro reo" (<ref-law>) kommt in der vom Beschwerdeführer angerufenen Funktion als Beweiswürdigungsregel im Verfahren vor Bundesgericht keine über das Willkürverbot von <ref-law> hinausgehende Bedeutung zu (<ref-ruling> E. 7 S. 82 mit Hinweisen).
Die Rüge der Verletzung von Grundrechten (einschliesslich Willkür bei der Sachverhaltsfeststellung) muss in der Beschwerde anhand des angefochtenen Entscheids präzise vorgebracht und substanziiert begründet werden, anderenfalls darauf nicht eingetreten wird (<ref-law>; <ref-ruling> E. 2.4 S. 368 mit Hinweisen).
2.3. Entgegen der Darstellung des Beschwerdeführers lässt die Vorinstanz nicht ausser Acht, dass er die Versicherungsleistungen nicht unmittelbar gestützt auf seine Angaben, sondern gestützt auf ärztliche Bescheinigungen erhalten hat. Sie lastet ihm jedoch an, diese Bescheinigungen durch seine Angaben, es gehe ihm äusserst schlecht und er könne nicht als Taxifahrer arbeiten, erwirkt zu haben. Dass der Beschwerdeführer diese Angaben nicht gemacht hätte, wird in der Beschwerde nicht behauptet. Die Feststellungen der Vorinstanz, es sei erstellt, dass der Beschwerdeführer gegenüber den Ärzten und Versicherern wiederholt geschildert habe, es gehe ihm äusserst schlecht und er könne nicht mehr als Taxifahrer arbeiten sowie dass diese Angaben zu einer ärztlich bescheinigten Arbeitsunfähigkeit geführt haben, sind nicht willkürlich.
2.4. Weiter erwägt die Vorinstanz, dass der Beschwerdeführer eigenen Aussagen zufolge ab Sommer 2008 bis Anfang 2011 für private Besuche mehrmals Strecken von Basel nach Frankfurt und nach Wiesbaden gefahren sei, belege, dass er längere Strecken fahren könne. Dies wird in der Beschwerde nicht beanstandet. Gerügt wird die Schlussfolgerung der Vorinstanz, dies stehe im krassen Gegensatz zu den vom Beschwerdeführer gegenüber den Ärzten gemachten Schilderungen seines Zustandes, denn er habe sich den Ärzten gegenüber letztmals im Februar 2008 geäussert. Die Vorinstanz lastet dem Beschwerdeführer nicht an, er hätte - ausser gegenüber Dr. med. C._ im Januar 2013 - nach Februar 2008 gegenüber den Ärzten Angaben zu seinem Gesundheitszustand gemacht. Hingegen hält sie fest, dass er gegenüber der A._ AG auch noch am 1. Juli 2009 behauptet habe, er leide unter Müdigkeit, Kraftlosigkeit, Kopfschmerzen, Konzentrationsstörungen, habe keine Energie und den Weg von rund hundert Metern vom Parkplatz bis zum Besprechungsort habe er kaum bewältigen können. Wenn die Vorinstanz feststellt, die Schilderung seines Zustandes stehe im Widerspruch dazu, dass er ab Sommer 2008 bis Anfang 2011 zugegebenermassen mehr als 14-mal nach Frankfurt und x-mal zu seiner damaligen Freundin nach Wiesbaden mit seinem Auto fuhr, verfällt sie nicht in Willkür.
2.5. Die Feststellung der Vorinstanz, der Beschwerdeführer habe die behandelnden Ärzte und Versicherungen über den Umfang der aus seiner depressiven Phase resultierenden Einschränkung der Arbeitsfähigkeit nicht richtig informiert, ist nicht willkürlich. Ob dies als Täuschung im Sinne von <ref-law> zu qualifizieren ist, ist keine Frage der Sachverhaltsfeststellung, sondern der rechtlichen Würdigung. Gleiches gilt für die Feststellung der Vorinstanz, die unrichtige Information der Ärzte durch den Beschwerdeführer habe eine seriöse Abklärung und Ermittlung seiner Arbeitsfähigkeit verhindert. Ob der Beschwerdeführer durch die unrichtigen Angaben zu seinem Gesundheitszustand die Ärzte irregeführt hat, ist ebenfalls eine Rechtsfrage. Dass das Invaliditätseinkommen mit Fr. 0.-- zu tief angesetzt worden ist, ist unbestritten. Ob der Beschwerdeführer aufgrund des zu tief angesetzten Invaliditätseinkommens Leistungen der Versicherungen bezogen hat, auf welche er keinen Anspruch hatte, ist ebenfalls eine Frage rechtlicher Natur. Mit diesen Einwänden rügt der Beschwerdeführer keine willkürliche Sachverhaltsfeststellung.
2.6. Die Versicherungen stellten für die Beurteilung des Leistungsanspruchs auf die ärztlichen Berichte ab, welche auf den Angaben des Beschwerdeführers basierten, so auch auf das von der IV-Stelle Basel-Stadt an Dr. med. D._ in Auftrag gegebene Gutachten. Sie erbrachten gestützt auf diese Informationen Versicherungsleistungen. Vor diesem Hintergrund ist die Feststellung der Vorinstanz nicht willkürlich, die Versicherungen hätten in Anbetracht der zahlreichen Arztberichte, persönlichen Fragebogen sowie den Angaben des Beschwerdeführers betreffend sein Befinden vorerst keinen Anlass gehabt, weitere Abklärungen über seine Arbeitsfähigkeit zu treffen.
3.
Der Beschwerdeführer wendet sich gegen die rechtliche Qualifikation seiner Tat als Betrug im Sinne von <ref-law>.
3.1. Gemäss <ref-law> macht sich des Betruges schuldig, wer in der Absicht, sich oder einen andern unrechtmässig zu bereichern, jemanden durch Vorspiegelung oder Unterdrückung von Tatsachen arglistig irreführt oder ihn in einem Irrtum arglistig bestärkt und so den Irrenden zu einem Verhalten bestimmt, wodurch dieser sich selbst oder einen andern am Vermögen schädigt. Handelt der Täter gewerbsmässig, so wird er mit Freiheitsstrafe bis zu zehn Jahren oder Geldstrafe nicht unter 90 Tagessätzen bestraft (Abs. 2).
Der Tatbestand erfordert eine arglistige Täuschung. Betrügerisches Verhalten ist strafrechtlich nur relevant, wenn der Täter mit einer gewissen Raffinesse oder Durchtriebenheit täuscht. Dieses Erfordernis ist erfüllt, wenn der Täter ein ganzes Lügengebäude errichtet oder sich besonderer Machenschaften oder Kniffe bedient. Einfache falsche Angaben erfüllen das Merkmal der Arglist, wenn deren Überprüfung nicht oder nur mit besonderer Mühe möglich oder nicht zumutbar ist, sowie dann, wenn der Täter das Opfer von der möglichen Überprüfung abhält oder er nach den Umständen voraussieht, dass dieses die Überprüfung der Angaben aufgrund eines besonderen Vertrauensverhältnisses unterlassen werde. Soweit das Täuschungsopfer den Irrtum mit einem Mindestmass an Aufmerksamkeit hätte vermeiden können, ist die Täuschung nicht arglistig. Ob die Täuschung arglistig ist, beurteilt sich unter Berücksichtigung der jeweiligen Schutzbedürftigkeit des Täuschungsopfers bzw. seiner allenfalls vorhandenen besonderen Fachkenntnis und Geschäftserfahrung im Einzelfall. Der Tatbestand erfordert indessen nicht, dass das Täuschungsopfer die grösstmögliche Sorgfalt walten lässt und alle erdenklichen Vorkehren zu seinem Schutz trifft. Arglist scheidet nur ausnahmsweise aus, nämlich wenn das Opfer leichtfertig die grundlegendsten Vorsichtsmassnahmen nicht beachtet, so dass das täuschende Verhalten des Täters in den Hintergrund tritt (<ref-ruling> E. 2.2.2 S. 154 ff.; <ref-ruling> E. 5.2 S. 79 ff.; je mit Hinweisen).
Nach der im Bereich der Sozialhilfe ergangenen Rechtsprechung, die auch im Sozialversicherungsrecht Anwendung findet, handelt eine Behörde leichtfertig, wenn sie eingereichte Belege nicht prüft oder es unterlässt, die um Sozialhilfe ersuchende Person aufzufordern, die für die Abklärung der Einkommens- und Vermögensverhältnisse relevanten Unterlagen einzureichen. Leichtfertigkeit wird namentlich angenommen, wenn die Behörde den Gesuchsteller nicht zu den von ihm vorgetragenen widersprüchlichen Angaben befragt (Urteil 6B_125/2012 vom 28. Juni 2012 E. 5.3.3 mit Hinweisen).
3.2. Der Beschwerdeführer rügt, die Vorinstanz habe in Verletzung von <ref-law> die Täuschung bejaht. Seiner Argumentation legt der Beschwerdeführer nicht den von der Vorinstanz festgestellten Sachverhalt zugrunde, sondern stellt auf seine eigene Sichtweise der Ereignisse ab. Er geht bei seiner rechtlichen Argumentation davon aus, seine Angaben gegenüber den Ärzten seien nicht unwahr gewesen, ohne das gegenteilige Beweisergebnis der Vorinstanz als willkürlich zu rügen und ohne sich argumentativ mit den entsprechenden Erwägungen des angefochtenen Entscheids auseinanderzusetzen. Er unterlässt es auch, durch präzise Hinweise auf konkrete Aktenstücke seine Behauptung zu belegen.
Die Vorinstanz legt willkürfrei dar, weshalb sie es als erstellt erachtet, dass der Beschwerdeführer den Ärzten und den Versicherungen gegenüber unzutreffende Angaben über seinen gesundheitlichen Zustand gemacht hat. Indem der Beschwerdeführer seinen Gesundheitszustand als derart schlecht schilderte, dass ihm Arbeitsunfähigkeit ärztlich attestiert wurde, täuschte er die Ärzte. Durch das Vorspiegeln eines falschen Gesundheitszustandes gegenüber den Ärzten hat er mittelbar, durch die von jenen erstellten Gutachten, auch die Versicherungen getäuscht (vgl. Urteil 6B_46/2010 vom 19. April 2010 E. 4.3). Zudem täuschte er die Versicherungen unmittelbar durch die direkt ihnen gegenüber gemachten falschen Angaben.
3.3. Weiter macht der Beschwerdeführer geltend, die Vorinstanz werfe ihm vor, er habe die Versicherungen nicht über seine Tätigkeit respektive über die Wiederaufnahme von Arbeitsversuchen informiert. Somit gehe sie von einer Täuschung durch Unterlassen aus. Dies sei unzulässig, da Betrug durch Unterlassen eine Garantenstellung erfordere und eine solche gemäss bundesgerichtlicher Rechtsprechung in Bezug auf die Informationspflicht des Bezügers nicht bestehe.
Nur wenn sich das Verhalten des Bezügers von Versicherungsleistungen in der Missachtung von gesetzlichen und vertraglichen Meldepflichten erschöpft, d.h. wenn der Bezüger keine unwahren Angaben macht bzw. kein anderes aktives Verhalten vorliegt, verneint das Bundesgericht eine Täuschungshandlung (<ref-ruling> E. 2.4 S. 14 f.). Die Vorinstanz bejaht Täuschung im Sinne von <ref-law> nicht allein deswegen, weil der Beschwerdeführer seinen Meldepflichten nicht nachgekommen ist. Vielmehr bejaht sie die Täuschung mit der Begründung, der Beschwerdeführer habe einerseits den Ärzten gegenüber und anderseits in seinen Erklärungen gegenüber den Versicherungen falsche Angaben über seinen Gesundheitszustand gemacht. Sie wirft ihm somit aktives Täuschungsverhalten vor. Die Rüge erweist sich als unbegründet.
3.4.
3.4.1. Der Beschwerdeführer ist der Ansicht, nicht arglistig gehandelt zu haben. Ihm kann nicht gefolgt werden. Soweit er seinen Ausführungen wiederum eine Unterlassung zugrunde legt, kann auf die obigen Ausführungen verwiesen werden (vgl. E. 3.3). In Bezug auf die IV-Stelle rügt der Beschwerdeführer, diese habe gestützt auf das Gutachten von Dr. med. D._ gewusst, dass er gearbeitet habe und habe es leichtfertig unterlassen, die zur Feststellung der Einkommensverhältnisse erforderlichen Abklärungen durchführen zu lassen, womit Arglist ausscheide. Die IV-Stelle Basel-Stadt beauftragte am 28. September 2007 Dr. med. D._ mit der Begutachtung des Beschwerdeführers. Dieser kam gestützt auf die Angaben des Beschwerdeführers zum Schluss, es liege eine Arbeitsunfähigkeit von 100 % vor, und zwar seit April 2005, da der Beschwerdeführer seither nur noch wenige Stunden Taxi gefahren sei. Gestützt auf dieses Gutachten verfügte die IV-Stelle Basel-Stadt am 15. September 2008 die rückwirkende Rentenzusprechung ab 1. April 2006. Durch das Inauftraggeben eines ärztlichen Gutachtens ist die IV-Stelle Basel-Stadt ihrer Pflicht zur Abklärung des Gesundheitszustandes des Beschwerdeführers nachgekommen. Aufgrund der gutachterlich attestierten Arbeitsunfähigkeit bestand für sie vorerst kein Anlass zu weiteren Abklärungen. Als Zweifel aufkamen, gab die IV-Stelle ein weiteres Gutachten bei Dr. med. C._ in Auftrag. Leichtfertiges Verhalten ist der IV-Stelle damit nicht vorzuwerfen.
3.4.2. Mit den weiteren Erwägungen der Vorinstanz hinsichtlich der Arglist setzt sich der Beschwerdeführer nicht argumentativ auseinander. Die Vorinstanz hält fest, dass die Ärzte bei der Diagnose einer depressiven Episode mit erhöhter Ermüdbarkeit und Konzentrationsstörungen bei der Ermittlung des Grads der Arbeitsunfähigkeit mangels organisch nicht nachweisbarer pathologischer Befunde in hohem Mass auf die Angaben des Patienten angewiesen waren. Diese Feststellung ist zutreffend. Der Gutachter ist für seine Diagnose auf die Schilderungen des Exploranden angewiesen und darf sich grundsätzlich darauf verlassen (vgl. Urteil 6B_46/2010 vom 19. April 2010 E. 4.3). Der Beschwerdeführer spiegelte einen Krankheitszustand vor, der so nicht bestand. Den Fachleuten war eine Überprüfung der Angaben des Beschwerdeführers nicht möglich oder jedenfalls mit einem unzumutbaren Aufwand verbunden (Urteil 6B_202/2010 vom 31. Mai 2010 E. 5.4.1, nicht publ. in: <ref-ruling>). Dies ergibt sich nach den zutreffenden vorinstanzlichen Erwägungen bereits aus dem Umstand, dass erst als die fehlende Buchhaltung des Taxibetriebs des Beschwerdeführers festgestellt wurde, ernsthafte Zweifel an der behaupteten 100-prozentigen Arbeitsunfähigkeit aufkamen. Dies veranlasste die A._ AG dazu, eine Observation und die IV-Stelle Basel-Stadt, ein weiteres Gutachten (erstellt am 2. Februar 2013 durch Dr. med. C._) in Auftrag zu geben. Wenn die Vorinstanz eine arglistige Täuschung bejaht, verletzt sie kein Bundesrecht.
3.5. Der Beschwerdeführer rügt, die vorinstanzliche Sachverhaltsfeststellung sei hinsichtlich der Frage der Arbeitsfähigkeit unvollständig, weshalb es an einer Voraussetzung für einen Schuldspruch wegen Betrugs fehle.
3.5.1. Eine Verurteilung wegen Betrugs setzt einen Vermögensschaden voraus. Im Sozialversicherungsrecht ist ein Vermögensschaden gegeben, wenn der Versicherte auf die ausbezahlten Leistungen keinen Anspruch hatte (Urteil 6B_646/2012 vom 12. April 2013 E. 2.4.2). Ein Vermögensschaden liegt vor, wenn die Ärzte und Gutachter, hätten sie von den falschen Vorbringen des Beschwerdeführers und den von diesem verheimlichten Aktivitäten Kenntnis gehabt, zu einer anderen Beurteilung gelangt wären und im konkreten Fall die A._ AG, die Invalidenversicherung und das Amt für Sozialbeiträge gestützt darauf zumindest eine volle Versicherungsleistung verweigert hätten. Dabei muss nicht eine effektive Arbeitstätigkeit über 30 % (betreffend die Leistungen der Invalidenversicherung und des Amtes für Sozialbeiträge) bzw. 33,33 % (betreffend die A._ AG) nachgewiesen werden, sondern lediglich eine Arbeitsfähigkeit in diesem Umfang (Urteil 6B_519/2011 vom 20. Februar 2012 E. 3.2).
Der Beweis für die Arbeitsfähigkeit in diesem Umfang kann entweder über den Nachweis einer effektiv ausgeübten Tätigkeit erbracht werden oder aber mit hypothetischen Überlegungen basierend auf medizinischen Erkenntnissen. Im letztgenannten Fall ist von einem Vermögensschaden dann auszugehen, wenn aus medizinischer Sicht schlüssig feststeht, dass in Kenntnis des wahren Gesundheitszustandes des Beschwerdeführers nicht von einem Invaliditätsgrad von mindestens 70 % bzw. 66.66 % auszugehen gewesen wäre und dieser somit nicht Anspruch auf die vollen Versicherungsleistungen gehabt hätte (Urteil 6B_519/2011 vom 20. Februar 2012 E. 3.2). Hinsichtlich des Beweiswertes eines Arztzeugnisses ist entscheidend, ob es für die strittigen Belange umfassend ist, auf allseitigen Untersuchungen beruht, auf die geltend gemachten Beschwerden des Exploranden eingeht, in der Beurteilung der medizinischen Situation einleuchtet, in Kenntnis der Vorakten (Anamnese) abgegeben worden ist und die Schlussfolgerungen des Experten begründet sind (<ref-ruling> E. 5.1 S. 232 mit Hinweis).
3.5.2. Die Vorinstanz bejaht einen Vermögensschaden für die gesamte gemäss ihrer Feststellung angeklagte Zeitspanne vom 29. April 2005 bis zum 31. Dezember 2010 mit der Begründung, das Invalideneinkommen sei aufgrund der unzutreffenden Angaben des Beschwerdeführers mit Fr. 0.-- zu tief und dementsprechend der Invaliditätsgrad entschieden zu hoch angesetzt worden, worauf die Versicherungen Leistungen erbracht hätten, auf welche der Beschwerdeführer keinen Anspruch gehabt habe.
Dass der Beschwerdeführer in Bezug auf die gesamte inkriminierte Zeitspanne seinen Gesundheitszustand dramatisiert und den Ärzten und Versicherungen gegenüber wiederholt falsche Angaben gemacht hat, ist willkürfrei erstellt. Dies allein genügt aber für einen Schuldspruch wegen Betrugs nicht. Entscheidend ist, ob dem Beschwerdeführer auch nachgewiesen werden kann, dass er in der inkriminierten Zeitspanne (oder einem Teil davon) zu mehr als 30 % bzw. 33,33 % arbeitsfähig war, denn nur dann wären die Leistungen der Versicherungen ohne Rechtsanspruch erfolgt.
3.5.3. Nach <ref-law> müssen beim Bundesgericht anfechtbare Entscheide die massgebenden Gründe tatsächlicher und rechtlicher Art enthalten. Der vorinstanzliche Entscheid muss somit aufzeigen, auf welchem festgestellten Sachverhalt er beruht und welche die auf den Sachverhalt angewendeten rechtlichen Überlegungen sind (<ref-ruling> E. 8.2 S. 153 mit Hinweisen). Nach der bundesgerichtlichen Rechtsprechung ist die Begründung insbesondere mangelhaft, wenn der angefochtene Entscheid jene tatsächlichen Feststellungen nicht trifft, die zur Überprüfung des eidgenössischen Rechts notwendig sind oder wenn die rechtliche Begründung des angefochtenen Entscheides so lückenhaft oder unvollständig ist, dass nicht geprüft werden kann, wie das eidgenössische Recht angewendet wurde. Die Begründung ist ferner mangelhaft, wenn einzelne Tatbestandsmerkmale, die für die Subsumtion unter eine gesetzliche Norm von Bedeutung sind, von der Vorinstanz nicht oder nicht genügend abgeklärt wurden (<ref-ruling> E. 5b S. 287 mit Hinweis).
3.5.4. In tatsächlicher Hinsicht trifft die Vorinstanz die erforderlichen tatsächlichen und rechtlichen Feststellungen nicht für die gesamte angeklagte Zeitspanne (29. April 2005 bis 31. Dezember 2010), sondern lediglich für die Zeit ab dem Jahr 2008 bis 31. Dezember 2010. Mit Ausnahme des als einfacher Betrug angeklagten Bezugs von Prämienbefreiungsleistungen zum Nachteil der A._ AG (zwischen dem 9. November 2005 und dem 12. Juni 2006) fallen die als Betrug angeklagten Leistungsbezüge sowohl in die Zeit vor dem Jahr 2008 als auch danach.
Die Vorinstanz gibt in ihren Erwägungen das Gutachten von Dr. med. C._ vom 2. Februar 2013 wieder, in welchem der Gutachter zum Schluss gelangt, der Beschwerdeführer sei ab dem Jahr 2008 bis Januar 2013 lediglich zu 40 % arbeitsunfähig gewesen. Weiter bezieht sich die Vorinstanz auf das Urteil des Sozialversicherungsgerichts vom 23. Juni 2014 in welchem - ebenfalls gestützt auf das Gutachten von Dr. med. C._ - von einer 40-prozentigen Beeinträchtigung der Arbeitsfähigkeit zwischen 2008 und dem Untersuchungstermin im Januar 2013 ausgegangen wird.
Die von Dr. med. C._ diagnostizierten Befunde sowie die attestierte 60-prozentige Arbeitsfähigkeit sind nachvollziehbar und gut begründet. Dr. med. C._ hat den Beschwerdeführer untersucht und eine sorgfältige - mit fremdanamnestischen Angaben ergänzte - Anamnese erstellt, welche die vom Beschwerdeführer geschilderten Symptome berücksichtigt und sich mit den Feststellungen in den Vorakten befasst (vgl. auch entsprechende Feststellungen im rechtskräftigen Urteil des Sozialversicherungsgerichts des Kantons Basel-Stadt vom 23. Juni 2014). Auf die Expertise vom 2. Februar 2013, welche dem Beschwerdeführer ab dem Jahr 2008 bis Januar 2013 eine Arbeitsunfähigkeit von lediglich 40 % attestiert, kann abgestellt werden. Für die angeklagte Zeitspanne seit dem Jahr 2008 bis 31. Dezember 2010 geht die Vorinstanz somit zu Recht von einer Arbeitsfähigkeit des Beschwerdeführers von 60 % aus. War aber der Beschwerdeführer in dieser Zeitspanne zu 60 % arbeitsfähig, hatte er keinen Anspruch auf die erhaltenen Versicherungsleistungen. Demzufolge ist in der Höhe der in dieser Periode zu Unrecht bezogenen Leistungen den Versicherungen ein Vermögensschaden entstanden. Die rechtliche Qualifikation als teilweise versuchter gewerbsmässiger Betrug (zum Nachteil der A._ AG und der Invalidenversicherung) sowie als einfacher Betrug (zum Nachteil des Amtes für Sozialbeiträge) ist zutreffend.
Der Schuldspruch des Beschwerdeführers in Bezug auf die Zeitspanne ab dem Jahr 2008 bis Ende Jahr 2010 wegen teilweise versuchten gewerbsmässigen Betrugs sowie wegen einfachen Betrugs verletzt kein Bundesrecht. Die Beschwerde ist diesbezüglich abzuweisen.
3.5.5. Die Vorinstanz kommt allerdings ihrer Begründungspflicht insofern nicht nach, als sie für die Zeitspanne vom 29. April 2005 bis Ende 2007 nicht die notwendigen Sachverhaltsfeststellungen vornimmt bzw. hat vornehmen lassen. Dem Urteil der Vorinstanz ist weder zu entnehmen, dass sie gestützt auf das Beweisergebnis davon ausginge, der Beschwerdeführer hätte in dieser Zeit tatsächlich zu über 30 % bzw. 33,33 % gearbeitet, noch führt sie aus, weshalb die Feststellungen von Dr. med. C._ auch für die Zeit vor 2008 Geltung haben sollten. Es fehlen verlässliche medizinische Entscheidungsgrundlagen für die Zeit vor Anfang 2008. Ein medizinisches Gutachten, welches sich zum Ausmass der Arbeitsfähigkeit für die Zeit vor Anfang 2008 äussern würde, wurde nicht eingeholt. Es mangelt an Sachverhaltsfeststellungen zum Grad der Arbeitsfähigkeit des Beschwerdeführers in der Zeit vor Anfang 2008. Demzufolge lässt sich gestützt auf das bisherige Sachverhaltsfundament der vorinstanzliche Schuldspruch betreffend die in die Zeitspanne April 2005 bis Ende 2007 fallenden Anklagevorwürfe nicht auf seine Richtigkeit überprüfen, weshalb die Vorinstanz mit dem Schuldspruch für die Zeit vor Ende 2007 Bundesrecht verletzt. Diesbezüglich ist die Beschwerde gutzuheissen.
4.
Die Beschwerde ist teilweise, d.h. in Bezug auf die in die Zeitspanne vom 29. April 2005 bis Ende 2007 fallenden Anklagevorwürfe, gutzuheissen. Dies betrifft vollumfänglich den Schuldspruch wegen einfachen Betrugs in Bezug auf die Prämienbefreiungsleistungen der A._ AG (angeklagte Leistungsbezüge vom 9. November 2005 bis 12. Juni 2006) sowie die Schuldsprüche wegen teilweise versuchten gewerbsmässigen Betrugs (zum Nachteil der A._ AG und der Invalidenversicherung) und wegen einfachen Betrugs (zum Nachteil des Amtes für Sozialbeiträge Basel-Stadt), welchen Leistungsbezüge vor Anfang 2008 zugrunde liegen. Das angefochtene Urteil ist diesbezüglich zur neuen Entscheidung an die Vorinstanz zurückzuweisen.
Im Übrigen - d.h. in Bezug auf die Schuldsprüche wegen teilweise versuchten gewerbsmässigen Betrugs (zum Nachteil der A._ AG und der Invalidenversicherung) und wegen einfachen Betrugs (zum Nachteil des Amtes für Sozialbeiträge Basel-Stadt), welchen Leistungsbezüge ab Anfang 2008 bis 31. Dezember 2010 zugrunde liegen - ist die Beschwerde abzuweisen.
5.
Der Beschwerdeführer wird im Umfang seines Unterliegens kostenpflichtig (<ref-law>). Der Beschwerdeführer ersucht um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung. Das Gesuch ist gegenstandslos geworden, soweit die Beschwerde gutzuheissen ist; im Übrigen ist es wegen Aussichtslosigkeit abzuweisen (Art. 64 Abs. 1 und 2 BGG). Der finanziellen Lage des Beschwerdeführers ist bei der Festsetzung der Höhe der Gerichtskosten Rechnung zu tragen (<ref-law>). Der Kanton Basel-Stadt trägt keine Kosten (<ref-law>), hat jedoch den Beschwerdeführer im Umfang dessen Obsiegens für das bundesgerichtliche Verfahren zu entschädigen (Art 68 Abs. 1 und 2 BGG). Die Entschädigung ist praxisgemäss dem Rechtsvertreter des Beschwerdeführers auszurichten.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen. Das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 13. Mai 2016 wird aufgehoben, soweit es die Verurteilung des Beschwerdeführers für die in der Zeitspanne vom 29. April 2005 bis Ende 2007 fallenden Anklagevorwürfe betrifft, und die Sache wird diesbezüglich im Sinne der Erwägungen zu neuer Entscheidung an die Vorinstanz zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen, soweit es nicht gegenstandslos geworden ist.
3.
Dem Beschwerdeführer werden Gerichtskosten von Fr. 800.-- auferlegt.
4.
Der Kanton Basel-Stadt hat dem Rechtsvertreter des Beschwerdeführers für das bundesgerichtliche Verfahren eine Parteientschädigung von Fr. 1'500.-- zu bezahlen.
5.
Dieses Urteil wird den Parteien, dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, und der IV-Stelle Basel-Stadt, schriftlich mitgeteilt.
Lausanne, 17. März 2017
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Schär