Faits:
A.
Par jugement du 10 février 2012, le Tribunal d'application des peines et des mesures du canton de Genève (ci-après : TAPEM) a ordonné la révocation de la libération conditionnelle de l'internement de X._ et sa réintégration dans la mesure d'internement, constaté que la mesure thérapeutique institutionnelle en milieu fermé qui avait été ordonnée durant le délai d'épreuve s'était soldée par un échec et invité le Service d'application des peines et mesures (ci-après : SAPEM) à trouver un autre établissement pénitentiaire susceptible d'accueillir le plus rapidement possible X._ afin de le changer de lieu de vie.
B.
Par arrêt du 9 mai 2013, la Chambre pénale d'appel et de révision de la Cour de justice genevoise a partiellement admis l'appel de X._, ordonné qu'il soit soumis à un traitement institutionnel dans un établissement psychiatrique approprié, chargé le SAPEM d'organiser son transfert et rejeté ses conclusions en indemnisation.
En bref, il en ressort les éléments suivants.
B.a. Le 15 février 2005, dans les locaux de l'Université de Genève, X._ a menacé d'un couteau un individu qui lui était inconnu, croyant que celui-ci travaillait pour les services de renseignements ou pour la police. Dans le cadre de l'instruction, une expertise psychiatrique a été ordonnée. L'expert, qui n'avait pas été en mesure de s'entretenir avec X._, a indiqué que ce dernier souffrait d'un trouble délirant persécutoire devenu chronique, assimilable à une maladie mentale et a conclu à son irresponsabilité. Il a précisé que X._ présentait un risque élevé de comportements hétéro-agressifs et qu'il avait besoin d'un traitement psychiatrique à long terme, sous forme d'hospitalisation, de traitements médicamenteux et de psychothérapie, ces traitements n'étant pas possibles sans sa collaboration. La Chambre d'accusation genevoise a, par ordonnance du 30 janvier 2007, constaté l'irresponsabilité de X._, prononcé un non-lieu et ordonné son internement.
B.b. Lors du premier contrôle de la mesure d'internement, le TAPEM a ordonné une nouvelle expertise. Dans son rapport du 24 février 2009, la Dresse A._ a indiqué que l'expertise avait été réalisée exclusivement sur dossier, X._ refusant d'entrer en contact avec elle. L'experte a confirmé la présence d'un trouble délirant persistant, soit une pathologie mentale grave, chronique, non reconnue par l'expertisé et non traitée, avec une composante hétéro-agressive imprévisible et importante. Le risque de récidive était le même qu'en 2006 et restait élevé en l'absence de prise en charge. Il n'y avait pas d'amélioration spontanée à espérer ni de sollicitation à attendre de la part de l'expertisé pour des soins. Le risque évolutif à craindre était une aggravation des aspects déficitaires de l'expertisé, des compensations psychotiques graves et des passages à l'acte hétéro-agressifs. Dans la mesure où le milieu carcéral pouvait être source d'aggravation de pathologies psychiatriques, en particulier psychotiques, le risque d'aggravation augmentait encore avec une incarcération prolongée. Il était indiqué que l'expertisé bénéficie d'une prise en charge psychiatrique longue, constante, comportant certes un risque de violence mais pouvant permettre l'administration régulière d'un traitement neuroleptique injectable. Idéalement, il s'agirait d'un espace médicalisé, très contenant, sécurisé, qui permettrait l'administration rapide d'un traitement sous contrainte, dès que nécessaire. Selon l'experte, l'internement devait être levé au bénéficie d'un traitement institutionnel en milieu fermé, afin que l'expertisé puisse accéder à des soins psychiatriques et notamment à une médication régulière.
Par jugement du 24 avril 2009, le TAPEM a levé conditionnellement l'internement de X._, fixé le délai d'épreuve à cinq ans et ordonné que ce dernier soit soumis à une mesure thérapeutique institutionnelle en milieu fermé.
B.c. En mai 2011, X._ a requis la levée de la mesure thérapeutique institutionnelle en milieu fermé. En septembre 2011, le ministère public a, quant à lui, requis la réintégration de X._ dans la mesure d'internement. Ces deux procédures ont été jointes et ont fait l'objet du jugement du TAPEM du 10 février 2012.
Dans le cadre de cette procédure, le SAPEM a émis l'avis que le traitement institutionnel en milieu fermé était inapplicable et une mesure d'internement semblait plus adaptée, le potentiel de dangerosité de X._ n'étant pas quantifiable.
La Commission d'évaluation de la dangerosité a, quant à elle, estimé que X._ présentait un caractère dangereux pour la société, la mise en oeuvre d'une nouvelle expertise psychiatrique n'étant pas nécessaire dans la mesure où l'intéressé refusait de communiquer avec l'expert.
Selon les deux certificats médicaux du 8 juillet et 1 er novembre 2011 de l'Unité de psychiatrie pénitentiaire de B._, X._ refusait systématiquement de consulter un médecin psychiatre et était vu une fois par mois dans sa cellule. Il évitait tout contact visuel et restait mutique lorsqu'un psychiatre essayait de lui parler, voire lui ordonnait sur un ton agressif de quitter sa cellule. Il restait isolé, replié sur lui-même, sans contact avec les autres détenus. Les gardiens ne notaient pas de comportement agressif, ni suicidaire. Il n'était pas non plus agressif avec le personnel soignant. En raison de sa faible alimentation, il présentait des carences vitaminiques et des troubles électrolytiques, qui faisaient obstacle à l'administration de neuroleptiques. Ces carences et ces troubles avaient des répercussions sur le rythme cardiaque. Dans leur audition devant le TAPEM, les médecins de l'unité de médecine pénitentiaire et de l'unité de psychiatrie ont indiqué qu'en raison des troubles physiques de X._, l'administration de neuroleptiques, qui pouvaient aggraver les problèmes cardiaques, devait se faire sous strict contrôle médical et donc dans un milieu hospitalier.
Dans le cadre de la procédure de deuxième instance cantonale, une nouvelle expertise psychiatrique a été ordonnée. Les experts ont relevé, dans leur rapport du 29 novembre 2012, que l'expertise ne reposait sur aucune constatation clinique, dès lors qu'ils n'avaient pas pu rencontrer l'expertisé. Ils ont confirmé le diagnostic de trouble délirant persistant qualifié de sévère.
Au sujet du risque de passage à l'acte violent, les experts ont observé qu'habituellement une telle évaluation reposait avant tout sur l'analyse des actes réels commis antérieurement par le sujet et des circonstances de ceux-ci. En l'espèce, à teneur du dossier, l'expertisé n'avait jamais blessé grièvement quelqu'un dans le cadre de sa pathologie. L'inquiétude qu'il puisse le faire était cependant manifeste dans les années 2004 et 2005. Elle était aussi relayée par la première expertise de 2005 et par les manifestations d'irritabilité, voire d'agressivité, manifestées par l'expertisé en prison, en relation avec sa pathologie, qui n'étaient cependant pas allées au-delà de menaces verbales, d'insultes et de crachats. Le risque de violence était en lien avec l'interprétativité à caractère persécutoire présentée par l'expertisé qui avait le sentiment de devoir se défendre face à ce qu'il percevait être des menaces ou des attaques. Cette altération de la compréhension de la réalité, associée au déni du potentiel de violence intrinsèque, fondaient la part principale des inquiétudes quant à la commission ultérieure d'un acte de violence par l'expertisé. La survenance d'un tel acte apparaissait comme imprévisible et donc peu prédictible. L'expertisé avait manifesté dans les faits une réalité de violence aux conséquences peu élevées, mais continuait de susciter des craintes d'un potentiel de violence plus marqué. Cette crainte était sans doute à relier à la dimension d'imprévisibilité qu'impliquait la présence d'un trouble mental. Les experts ont souligné l'importance du cadre de vie dans l'appréciation de la dangerosité, dès lors qu'un environnement perçu comme menaçant donnait prise aux interprétations délirantes et accroissait le risque de manifestations de violence. En résumé, les experts ont retenu que X._ pouvait être susceptible de commettre des actes de violence vis-à-vis d'autrui de manière imprévisible, en fonction de l'intensité de son vécu persécutoire pathologique et des situations dans lesquelles il pouvait se retrouver. L'intensité du risque était très difficile à évaluer. En l'absence de tout traitement, le risque serait selon toute vraisemblance élevé. Dans le cadre d'un environnement favorable au long cours, ce risque était vraisemblablement amoindri.
Quant au traitement, les experts ont relevé qu'une médication psychotrope et neuroleptique était souvent peu satisfaisante mais non négligeable. L'espoir de briser la résistance pathologique par une médication imposée, même de longue durée, n'était pas considéré comme une alternative crédible d'un point de vue thérapeutique. Un traitement psychiatrique intégré, de longue durée, comprenant une composante pharmacologique et une composante psychothérapeutique, se déroulant dans un environnement adapté, représentait la seule solution adéquate, même si ses chances de succès restaient faibles, au vu de l'évolution antérieure, mais n'apparaissaient pas nulles. L'administration de médicaments par la contrainte ne pouvait intervenir qu'en cas d'incapacité de discernement du patient en raison de son trouble mental et d'un risque vital imminent auto ou hétéro-agressif en lien avec ce trouble, ces deux aspects étant cumulatifs. Une fois ce risque passé, les conditions n'étaient plus remplies. De plus, des considérations d'ordre éthique, liées notamment aux nombreux effets secondaires des médicaments neuroleptiques, et l'état de santé physique de l'expertisé qui s'était détérioré à l'occasion des jeûnes répétés, faisaient aussi obstacle à l'administration d'un traitement pharmacologique par la contrainte.
Selon les experts, l'environnement carcéral n'était pas adapté et un changement d'établissement de détention ne paraissait donc pas susceptible d'apporter une réponse supplémentaire, seule la dimension sécuritaire y trouvant son compte. Comme préconisé par l'experte en 2009, c'était un environnement thérapeutique auquel il fallait avoir recours. C'était un établissement de soins ou de mesures qui était le plus adapté d'un point de vue thérapeutique, un traitement en milieu carcéral étant voué à l'échec. Dans un établissement psychiatrique, le risque de commission d'actes hétéro-agressifs n'était pas à exclure. La situation était marquée par une importante part d'imprévisibilité et une forte incertitude. Le risque était lié au vécu persécutoire pathologique et conséquemment au besoin que l'expertisé pouvait ressentir de se défendre de menaces ou d'attaques perçues comme telles par lui. Un cadre suffisamment sécurisé mais à vocation primairement thérapeutique, psychiatrique et somatique, était nécessaire compte tenu de la pathologie présentée par l'expertisé. Dans un premier temps, il s'agirait d'un établissement à vocation thérapeutique, mais fermé.
Dans un complément d'expertise du 1 er mars 2013, les experts ont relaté leur rencontre avec l'expertisé qui avait duré une quinzaine de minutes et s'était déroulée dans sa cellule. Les experts n'avaient décelé, dans le regard de l'expertisé qui n'avait pas dit un mot, aucune animosité, mais plutôt une vive curiosité, voire un intérêt. Ils avaient eu l'impression qu'il restait attentif aux paroles et les comprenait. Au bout de quelques minutes, l'expertisé, qui était assis à une table et écrivait, s'était allongé sur son lit, avait remonté sa couverture et fermé les yeux, en donnant l'impression qu'il exprimait ainsi son refus d'entrer en contact avec les experts, refus sans compromis, mais aussi sans manifestation de violence. Pour les experts, cette entrevue ne modifiait pas leurs conclusions sur le diagnostic. S'agissant du risque de récidive, ils ont relevé que si ce contact ne permettait pas une appréciation significative plus précise, au vu des circonstances (absence de dialogue en particulier), il était apparu que l'expertisé avait pu manifester son opposition à leur présence sans ambiguïté, mais également sans manifestation ouverte d'agressivité ou d'hostilité. Par ailleurs, l'apparente fragilité physique de l'expertisé paraissait susceptible de diminuer son potentiel de violence. Ces éléments paraissaient de nature à modérer quelque peu la probabilité actuelle de survenue d'une telle occurrence. Concernant la question de l'établissement adapté, les experts ont estimé que la première étape devait être hospitalière, permettant également un suivi de l'état somatique de l'expertisé, ce qui était impératif en cas d'introduction d'un traitement neuroleptique. Compte tenu de l'état physique actuel de l'expertisé, un établissement psychiatrique hospitalier permettant un accueil dans la durée était suffisant, la nécessité d'un établissement fermé ayant perdu quelque peu son aspect impératif. A priori, tout établissement psychiatrique hospitalier suisse remplissait ces conditions. Dans une phase ultérieure, un lieu de vie protégé, tel qu'un foyer psychiatrique, pouvait être envisagé, en fonction de l'évolution de la situation.
C.
C.a. Le Ministère public forme un recours en matière pénale au Tribunal fédéral contre l'arrêt du 9 mai 2013. Il conclut à sa réforme en ce sens qu'un traitement institutionnel en milieu fermé est ordonné à l'encontre de X._. Il requiert l'octroi de l'effet suspensif.
Le 23 juillet 2013, par ordre du juge instructeur de la Cour de droit pénal du Tribunal fédéral, l'effet suspensif a été accordé au recours à titre superprovisionnel en ce sens que jusqu'à décision sur la requête d'effet suspensif, aucune mesure d'exécution de la décision attaquée ne pourra être prise. Invité à se déterminer sur l'effet suspensif, X._ conclut à ce qu'il soit retiré au recours.
C.b. X._ forme un recours en matière pénale au Tribunal fédéral contre l'arrêt du 9 mai 2013. Il conclut, sous suite de dépens, à sa réforme en ce sens que la libération conditionnelle est confirmée, le délai d'épreuve étant fixé à cinq ans à compter du 24 avril 2009, qu'il est libéré de toute mesure thérapeutique et sa mise en liberté est ordonnée. Il conclut, en outre, à l'allocation d'une indemnité fixée à 400 fr. par jour de détention depuis le 12 mars 2007, soit au jour du dépôt du recours un montant de 914'800 francs. Il requiert par ailleurs l'assistance judiciaire.
Invités à déposer des observations sur le recours, la Cour cantonale y a renoncé et le Ministère public a conclu à son rejet.

Considérant en droit:
1.
Les deux recours ont pour objet la même décision. Ils ont trait au même complexe de faits. Il y a lieu de joindre les causes et de les traiter dans un seul arrêt (<ref-law> et 71 LTF).
I. Recours du Ministère public :
2.
Le ministère public fait grief à la cour cantonale d'avoir arbitrairement apprécié les preuves.
2.1. De jurisprudence constante, une décision, respectivement une appréciation, n'est pas arbitraire du seul fait qu'elle apparaît discutable ou même critiquable. Il faut qu'elle soit manifestement insoutenable ou, autrement dit, absolument inadmissible, et cela non seulement dans sa motivation mais dans son résultat (cf. <ref-ruling> consid. 1.3 p. 4 s.; <ref-ruling> consid. 5.4 p. 148 et les arrêts cités), ce qui, à peine d'irrecevabilité, doit être démontré dans le recours conformément aux exigences de motivation de l'<ref-law> (cf. <ref-ruling> consid. 1.4 p. 287). En matière d'appréciation des preuves et d'établissement des faits, il y a arbitraire (pour une définition de l'arbitraire, cf. <ref-ruling> consid. 6.1 p. 379 s.; <ref-ruling> consid. 2.4 p. 5) lorsque l'autorité n'a manifestement pas compris le sens et la portée d'un moyen de preuve, si elle ne prend pas en compte, sans raison sérieuse, un élément de preuve propre à modifier la décision ou lorsqu'elle tire des constatations insoutenables des éléments recueillis (<ref-ruling> consid. 2.1 p. 9; <ref-ruling> consid. 2a p. 41).
2.2. Comme tous les autres moyens de preuve, les expertises sont soumises à la libre appréciation du juge. Celui-ci ne peut cependant pas s'écarter d'une expertise sans motifs pertinents. Il doit examiner, en se fondant sur les autres moyens de preuve administrés et sur les arguments des parties, si de sérieuses objections font obstacle au caractère probant des conclusions de l'expertise. En se fondant sur une expertise non concluante, le juge peut tomber dans l'arbitraire (<ref-ruling> consid. 3.2 p. 547 s.).
Lorsque l'autorité cantonale juge une expertise concluante et en fait sien le résultat, le Tribunal fédéral n'admet le grief d'appréciation arbitraire que si l'expert n'a pas répondu aux questions posées, si ses conclusions sont contradictoires ou si, d'une quelconque autre façon, l'expertise est entachée de défauts à ce point évidents et reconnaissables, même sans connaissances spécifiques, que le juge ne pouvait tout simplement pas les ignorer. Il n'appartient pas au Tribunal fédéral de vérifier si toutes les affirmations de l'expert sont exemptes d'arbitraire; sa tâche se limite bien plutôt à examiner si l'autorité de première instance pouvait, sans arbitraire, se rallier au résultat de l'expertise (arrêt 9C_717/2011 du 25 juin 2012 consid. 5.1).
2.3. Le ministère public reproche à la cour cantonale d'avoir fait siennes les conclusions du complément d'expertise du 1 er mars 2013 et d'avoir ordonné sur cette base un traitement institutionnel en milieu ouvert. La cour cantonale aurait procédé à une interprétation arbitraire des preuves dès lors que le complément d'expertise du 1 er mars 2013 serait entaché de défauts qu'elle ne pouvait ignorer. Tout d'abord, les nouvelles conclusions du complément se fonderaient sur un seul entretien de 15 minutes lors duquel l'intimé n'a pas prononcé un mot. Elles ne seraient ainsi pas crédibles, ce d'autant moins que le rapport d'expertise du 29 novembre 2012 se fondait sur une analyse minutieuse du volumineux dossier. Le complément comporterait en outre des contractions dès lors que les experts y indiqueraient, d'une part, qu'ils maintiennent leur diagnostic et leur appréciation sur l'évaluation de la dangerosité de l'intimé et, d'autre part, qu'un traitement en milieu fermé ne s'impose plus. Les conclusions du complément seraient également clairement contraires à celles du rapport du 29 novembre 2012 qui préconisait un traitement dans un établissement fermé, alors même qu'aucun élément nouveau ne viendrait expliquer ce revirement. En effet, l'état de santé de l'intimé, sur lequel se fonderaient les experts pour justifier leur changement de position, leur était déjà connu lors de l'établissement de leur rapport dans lequel ils avaient conclu à la nécessité d'un établissement fermé. Il ne ressortirait ni du complément, ni de la procédure que l'état de santé de l'intimé se serait dégradé entre le 29 novembre 2012 et le jour de l'entrevue au point d'annihiler tout potentiel dangereux de sa part. La cour cantonale aurait ainsi dû écarter le complément pour ne se fonder que sur les conclusions de l'expertise du 29 novembre 2012.
2.4. Si certes le complément d'expertise se base sur une rencontre de quelques minutes avec l'intimé, il n'en demeure pas moins que les experts n'avaient pas encore eu l'occasion de se rendre compte de visu de l'état de faiblesse physique de l'intimé et il s'agit d'un élément nouveau. De plus, leurs conclusions se fondent également sur le fait que, même si l'intimé n'a pas prononcé un mot, il a été capable de manifester son opposition sans agressivité, ni hostilité. Les experts indiquent ainsi que, sans rien retrancher de leur appréciation de la dimension d'imprévisibilité d'un potentiel passage à l'acte hétéro-agressif en lien avec le vécu persécutoire de l'intimé, les éléments susmentionnés apparaissent de nature à modérer quelque peu la probabilité actuelle de survenue d'une telle occurrence. On comprend donc que ces deux éléments, soit la faiblesse physique et la capacité de l'intimé à manifester son opposition sans agressivité, sont de nature à modérer le risque de violence de l'intimé, même si le diagnostic sur sa maladie mentale reste le même. On ne décèle aucune contradiction dans ce raisonnement. En effet, ce n'est pas la maladie en tant que telle qui amenait les experts à conclure à la nécessité d'un établissement fermé, mais bien plutôt leur évaluation du risque de passage à l'acte violent de l'intimé. Dès lors que ce risque est modéré par d'autres facteurs, il n'est pas contradictoire, à tout le moins pas manifestement insoutenable, de conclure qu'un établissement fermé ne se justifie plus actuellement. La cour cantonale pouvait donc se rallier, sans arbitraire, aux conclusions du complément d'expertise du 1 er mars 2013.
2.5. Le ministère public reproche à la cour cantonale d'avoir fait abstraction de certains éléments du dossier qui feraient référence à l'agressivité et la dangerosité de l'intimé (ton agressif, crachats, gestes menaçants rapportés par les médecins de l'unité de médecine pénitentiaire). Ce faisant, elle serait arrivée à une constatation insoutenable, soit que le potentiel de violence de l'intimé était amoindri et minime.
La cour cantonale n'a pas ignoré les éléments auxquels se réfère le ministère public. Elle a toutefois tenu compte de l'ensemble des circonstances (cf. infra consid. 2.2), en particulier du complément d'expertise du 1 er mars 2013. On notera en outre que les éléments auxquels se réfère le ministère public ne font état d'aucune violence physique de la part de l'intimé. De plus, ils sont nuancés par le fait qu'ils ont à chaque fois été commis lorsque le personnel soignant tentait de forcer l'intimé à faire quelque chose ou à collaborer (cf. certificats des 8 juillet et 1 er novembre 2011, déclarations des médecins traitants). Sur la base de l'ensemble de ces éléments, il n'était pas manifestement insoutenable de retenir que le potentiel de violence de l'intimé était amoindri.
3.
Le ministère public se plaint d'une violation de l'art. 59 al. 2 et 3 CP.
3.1. En règle générale, le traitement institutionnel s'effectue dans un établissement psychiatrique approprié ou dans un établissement d'exécution des mesures (<ref-law>). L'<ref-law> prévoit que, tant qu'il existe un risque de fuite ou de récidive, le traitement doit être exécuté dans un établissement fermé ; il peut aussi être effectué dans un établissement pénitentiaire au sens de l'<ref-law>, dans la mesure où le traitement thérapeutique nécessaire est assuré par du personnel qualifié (art. 59 al. 3 2 e phrase CP).
Pour qu'un risque de fuite soit avéré, il faut que l'intéressé ait la ferme et durable intention de s'évader, en ayant recours à la force si nécessaire, et qu'il dispose des facultés intellectuelles, physiques et psychiques nécessaires pour pouvoir établir un plan et le mener à bien. Le fait que l'intéressé puisse tenter de s'enfuir sur un coup de tête et sans aucune préparation préalable ne suffit pas. Il est clair que le risque de fuite devra être lié à la peur que le condamné puisse représenter une menace envers les tiers une fois en liberté. Il s'agit ici de la dangerosité externe du prévenu (arrêts 6B_372/2012 du 27 septembre 2012 consid. 2.3; 6B_629/2009 du 21 décembre 2009 consid. 1.2.2.2).
Le risque de récidive doit être concret et hautement probable, c'est-à-dire résulter de l'appréciation d'une série de circonstances. Il vise cette fois la dangerosité interne du prévenu. Au regard du principe de la proportionnalité, le placement dans un établissement fermé ne peut être ordonné que lorsque le comportement ou l'état du condamné représente une grave mise en danger pour la sécurité et l'ordre dans l'établissement. Ce sera, par exemple, le cas d'un condamné qui profère des menaces bien précises ou qui combat sciemment l'ordre de l'établissement ; en revanche, l'<ref-law> ne devrait pas s'appliquer à de simples difficultés de comportement ou à l'insoumission vis-à-vis des employés de l'établissement (arrêts 6B_372/2012 du 27 septembre 2012 consid. 2.3; 6B_629/2009 du 21 décembre 2009 consid. 1.2.2.2).
3.2. En substance, la cour cantonale a retenu que, compte tenu des conclusions des experts, interprétées à l'aide des explications fournies dans la discussion, le risque de récidive présenté par l'intimé était théoriquement important mais difficilement quantifiable et prédictible. Moyennant un traitement adéquat, qui n'avait jamais été prodigué sur le long terme, ce risque était susceptible de diminuer. L'intimé n'avait pas d'antécédents judiciaires connus, hormis l'agression à l'origine de la mesure et avait été libéré à deux reprises durant l'instruction de la procédure. Il avait aussi été hospitalisé contre son gré à la Clinique psychiatrique de C._ pendant une vingtaine de jours. Durant ces périodes, aucune manifestation de violence n'avait été constatée ou signalée à teneur du dossier. Selon les derniers rapports des médecins de médecine pénitentiaire de B._, l'intimé n'était pas agressif envers les gardiens ou les soignants, contrairement au début de son incarcération. L'état de santé physique de l'intimé, qui s'était notablement dégradé depuis 2009 selon ses médecins traitants, diminuait encore davantage l'éventuel potentiel de violence, comme le relevait l'expertise.
La cour cantonale a en outre indiqué que, s'il était vrai que les experts avaient retenu, dans leurs conclusions du 29 novembre 2012, qu'il convenait que l'établissement à vocation thérapeutique soit dans un premier temps un établissement fermé, ils avaient clairement affirmé que c'était un cadre hospitalier et non carcéral qui était nécessaire. Ils avaient d'ailleurs précisé leurs conclusions dans leur complément d'expertise du 1 er mars 2013, après avoir notamment constaté l'état de faiblesse physique de l'intéressé, et avaient estimé que n'importe quel établissement psychiatrique hospitalier suisse était indiqué.
La cour cantonale a enfin indiqué que, sur le vu des conclusions de l'expertise et d'une appréciation de toutes les circonstances du cas d'espèce, le risque de récidive ne pouvait être qualifié de concret et hautement probable. Quant à l'éventuel risque de fuite, qui supposait que le détenu ait la ferme intention de s'évader et dispose des facultés intellectuelles, physiques et psychiques nécessaires, rien n'indiquait que l'intimé avait la volonté et la capacité de s'évader et aucun élément du dossier ne venait conforter cette éventualité. Au regard des éléments susmentionnés et dans le strict respect du principe de proportionnalité, il se justifiait d'ordonner un traitement institutionnel dans un établissement psychiatrique approprié au sens de l'<ref-law>.
3.3. Se fondant sur les conclusions de l'expertise du 29 novembre 2012, le ministère public prétend que c'est à tort que la cour cantonale a retenu que le risque de récidive n'était ni concret, ni hautement vraisemblable. Il soutient que le cas serait comparable à celui traité dans l'arrêt 6B_274/2012 pour lequel le Tribunal fédéral avait jugé que le maintien de l'exécution du traitement institutionnel en milieu fermé était conforme au droit fédéral.
3.4. La cour cantonale a fondé son raisonnement notamment sur le complément d'expertise du 1 er mars 2013. Il en ressort en particulier que l'intimé peut commettre un acte hétéro-agressif en lien avec son vécu persécutoire de manière imprévisible, mais que la fragilité physique et la capacité de l'intimé à manifester son opposition sans hostilité sont de nature à modérer la probabilité actuelle de survenue d'une telle occurrence. La cour cantonale a également relevé que lors de l'instruction, l'intimé avait été libéré à deux reprises et qu'il avait également séjourné en clinique sans qu'il ne manifeste de violence durant ces périodes. Selon les derniers rapports des médecins, il n'était pas agressif envers les gardiens et le personnel soignant. Par conséquent, au vu des éléments retenus, la cour cantonale pouvait considérer qu'il n'était pas établi que le comportement ou l'état de l'intimé représentaient une grave mise en danger pour la sécurité et l'ordre dans l'établissement et en conclure que le risque de récidive n'était, en l'état, pas concret et hautement probable. S'agissant du risque de fuite, elle a retenu que rien n'indiquait que l'intimé avait la volonté et la capacité de s'évader. A cet égard, le ministère public ne formule aucune critique. Il se contente de se référer à l'arrêt 6B_274/2012. Bien que le trouble dont souffre l'intimé soit similaire à celui du cas traité dans cet arrêt, rien ne démontre que les autres circonstances aient été identiques, en particulier l'état physique des personnes concernées. Par conséquent, au vu de l'ensemble des circonstances, la cour cantonale, pouvait, sans violation du droit fédéral, ordonner une mesure institutionnelle au sens de l'<ref-law>. Comme l'a, à juste titre, rappelé la cour cantonale, l'<ref-law>, permet au juge de lever une mesure thérapeutique institutionnelle, avant ou pendant l'exécution de cette mesure, et d'ordonner, à la place, une autre mesure thérapeutique institutionnelle s'il est à prévoir que cette nouvelle mesure sera manifestement mieux à même de détourner l'auteur d'autres crimes ou délits en relation avec son état. Dans le cas d'espèce, il appartiendra aux autorités cantonales de surveiller attentivement l'évolution de l'intimé et, si son potentiel de dangerosité devait évoluer défavorablement, de faire application de l'<ref-law> pour ordonner son retour dans un établissement fermé.
4.
Le recours du ministère public doit être rejeté.
II. Recours de X._ :
5.
Le recourant revient sur la décision du TAPEM du 24 avril 2009 et prétend que la mesure thérapeutique institutionnelle instituée dans le cadre de cette décision serait illégale, dès lors que dite décision avait également prononcé sa libération conditionnelle de l'internement. En conséquence, sa libération immédiate devrait être ordonnée. Autre-ment dit, le recourant soutient que puisque le TAPEM avait ordonné sa libération conditionnelle, cette autorité n'était pas habilitée à instituer dans la même décision une mesure thérapeutique. Cette approche revient en quelque sorte à invoquer un cas de nullité de la mesure institutionnelle instituée en 2009, ce qui devrait conduire à la libération du recourant.
5.1. Par décision du 24 avril 2009, le TAPEM a ordonné la libération conditionnelle de l'internement du recourant, fixé un délai d'épreuve de 5 ans et ordonné qu'il soit soumis à une mesure thérapeutique institutionnelle en milieu fermé durant le délai d'épreuve.
S'agissant de la compétence du TAPEM, la cour cantonale a relevé que le fait que le changement de sanction ait été prononcé par le TAPEM et non par le juge ayant prononcé l'internement n'entachait pas la validité de cette décision, qui n'avait pas été contestée en son temps. Se référant à la doctrine, elle a estimé que l'exigence posée par l'<ref-law> semblait davantage procéder d'une inadvertance législative. La législation cantonale de l'époque conférait, comme encore aujourd'hui, la compétence d'ordonner un changement de sanction au TAPEM.
La cour cantonale a estimé que, nonobstant son dispositif, la décision du 24 avril 2009 s'apparentait à un changement de sanction au sens de l'<ref-law>, dans la mesure où le prononcé d'un traitement institutionnel en milieu fermé durant le délai d'épreuve de la libération conditionnelle de l'internement ne semblait pas être une solution conforme au système préconisé par le législateur. La libération conditionnelle de l'internement supposait d'ailleurs que l'on puisse prévoir que l'auteur se conduise correctement en liberté (<ref-law>). Or, en l'espèce, le recourant était demeuré dans le même établissement de détention, ce qui était difficilement compatible avec une libération conditionnelle.
5.2. Selon l'<ref-law>, l'auteur est libéré conditionnellement de l'internement dès qu'il est à prévoir qu'il se conduira correctement en liberté. Le délai d'épreuve est de deux à cinq ans. Une assistance de probation peut être ordonnée et des règles de conduite peuvent lui être imposées pour la durée de la mise à l'épreuve. Toutefois, contrairement à ce qui est prévu s'agissant de la libération conditionnelle d'une mesure institutionnelle (<ref-law>), la loi ne prévoit pas la possibilité d'imposer un traitement ambulatoire en tant que modalité de la libération conditionnelle d'un internement (cf. <ref-law>), pas plus qu'une mesure thérapeutique institutionnelle.
Aux termes de l'<ref-law>, si, avant ou pendant l'exécution d'une peine privative de liberté ou d'un internement au sens de l'<ref-law>, le condamné réunit les conditions d'une mesure thérapeutique institutionnelle prévues aux art. 59 à 61 CP, le juge peut ordonner cette mesure ultérieurement. Le juge compétent est celui qui a prononcé la peine ou ordonné l'internement (art. 65 al. 1 2 e phrase CP). S'agissant d'une décision ultérieure indépendante, la procédure est régie par les <ref-law> (cf. arrêt 6B_597/2012 du 28 mai 2013 consid. 2.3.1). La décision peut être attaquée par la voie du recours (cf. <ref-law>) à l'exclusion de l'appel ( MARIANNE HEER, in Basler Kommentar, Schweizerische Strafprozessordnung, 2011, n o 6 ad <ref-law>; MICHEL PERRIN, in Commentaire romand Code de procédure pénale suisse, 2011, n o 11 ad <ref-law>; CHRISTIAN SCHWARZENEGGER, in Kommentar zur Schweizerischen Strafprozessordnung, Donatsch/Hansjakob/Lieber [éd.], 2010, n o 3 ad <ref-law>; NIKLAUS SCHMID, Schweizerische Strafprozessordnung, Praxiskommentar, 2009, n o 4 ad <ref-law>).
5.3. Hormis dans les cas expressément prévus par la loi, il n'y a lieu d'admettre la nullité qu'à titre exceptionnel, lorsque les circonstances sont telles que le système d'annulabilité n'offre manifestement pas la protection nécessaire. Des vices de fond n'entraînent qu'à de rares exceptions la nullité d'une décision; en revanche, de graves vices de procédure, ainsi que l'incompétence qualifiée de l'autorité qui a rendu la décision sont des motifs de nullité (cf. <ref-ruling> consid. 4.4.3 p. 56; <ref-ruling> consid. 3.1 p. 275; <ref-ruling> consid. 3.1 p. 27; <ref-ruling> consid. 3.3 p. 434; <ref-ruling> consid. 2.1 p. 363; <ref-ruling> consid. 3a/aa p. 99). L'illégalité d'une décision ne constitue pas par principe un motif de nullité (<ref-ruling> consid. 2.4 p. 257).
5.4. La compétence du TAPEM est expressément prévue par la législation genevoise (cf. art. 3 let. r de l'ancienne loi genevoise d'application du code pénal suisse et d'autres lois fédérales en matière pénale du 17 novembre 2006, en vigueur en avril 2009; art. 3 let. v de la loi d'application du code pénal suisse et d'autres lois fédérales en matière pénale du 27 août 2009; RS/GE E 4 10). De manière générale, le TAPEM est l'autorité chargée de l'application des mesures. On ne peut ainsi pas parler d'incompétence matérielle ou fonctionnelle manifeste du TAPEM. En outre, la compétence du juge du fond selon l'<ref-law> pour traiter de la question de la transformation d'une peine ou d'un internement en mesure thérapeutique institutionnelle est discutée. Selon une approche doctrinale, il n'y a guère de raison, face à des situations évolutives comme le sont manifestement celles qui donnent lieu à l'application de l'<ref-law>, de privilégier la continuité (c'est-à-dire l'examen par le même juge) sur les apports du regard neuf qu'un autre juge pourrait porter sur ladite situation. En outre, cette règle empiète sur la compétence des cantons s'agissant de l'organisation judiciaire. Enfin, la loi n'impose pas la compétence du juge du fond s'agissant de la transformation d'une mesure thérapeutique institutionnelle en internement (cf. <ref-law>). L'<ref-law> correspondrait ainsi à une inadvertance législative (cf. ROBERT ROTH, in Commentaire romand, Code Pénal I, 2009, n o 21 ss ad <ref-law>). Il conviendrait même d'interpréter cette disposition à la lumière de l'<ref-law>, lex posterior, qui autorise les cantons à prévoir la compétence d'une autre autorité que le juge du fond en matière de décision judiciaire ultérieure indépendante (cf. MARIANNE HEER, in Basler Kommentar, Schweizerische Strafprozessordnung, 2011, n o 7 ad <ref-law>). Au vu de ce qui précède, on ne saurait envisager une incompétence qualifiée du TAPEM susceptible d'entraîner la nullité de sa décision du 24 avril 2009. Bien que dite décision soit antérieure à l'entrée en vigueur du CPP, il n'y a pas lieu d'interpréter différemment la situation.
5.5. Selon le recourant, le TAPEM a ordonné sa libération conditionnelle le 24 avril 2009. La cour cantonale ne pouvait ainsi pas interpréter cette décision de manière contraire à son sens clair. Venir soutenir, quatre ans après son prononcé, qu'en réalité cette libération conditionnelle n'en serait pas une, constituerait une violation du principe de l'autorité de la chose jugée et porterait atteinte aux attentes légitimes que le recourant avait placées dans cette décision qui prévoyait expressément un délai d'épreuve de cinq ans à l'issue duquel il serait libéré de manière définitive.
Certes, le prononcé d'une libération conditionnelle d'un internement pour passer à une mesure thérapeutique institutionnelle en milieu fermé n'est pas prévu par la loi. L'<ref-law> permet néanmoins la transformation d'un internement en mesure thérapeutique institutionnelle en milieu fermé. Ainsi, le résultat auquel a abouti la décision du 24 avril 2009, soit la transformation de l'internement en mesure thérapeutique institutionnelle, est prévu par la loi. Par conséquent, il n'existe aucun vice de fond susceptible d'entraîner la nullité de la décision du 24 avril 2009. Dans la mesure où cette décision ordonnait une mesure thérapeutique institutionnelle en milieu fermé, la cour cantonale pouvait, comme le prévoit l'<ref-law>, ordonner que cette mesure soit exécutée en milieu ouvert. Le grief est infondé.
6.
Invoquant les art. 3 et 5 CEDH, 56 al. 5 et 59 al. 2 et 3 CP et 1 al. 1 et 3 du règlement genevois sur le régime intérieur de la prison et le statut des personnes incarcérées (RRIP; RS/GE F 1 50.04), le recourant soutient que sa détention serait illégale. Il en déduit, fondé sur l'<ref-law>, qu'il aurait droit à une indemnité. Il reproche également à la cour cantonale de ne pas avoir établi les faits nécessaires, ni examiné ses griefs dûment soulevés devant la cour cantonale à cet égard en violation de l'<ref-law>.
6.1. Selon le recourant, sa détention serait illégale car contraire aux art. 56 al. 5 et 59 al. 2 et 3 CP.
6.1.1. En vertu de l'<ref-law>, en règle générale, le juge n'ordonne une mesure que si un établissement approprié est à disposition. Aux termes de l'<ref-law>, le traitement institutionnel des troubles mentaux s'effectue dans un établissement psychiatrique approprié ou dans un établissement d'exécution des mesures. Le législateur vise, en premier lieu, les cliniques psychiatriques publiques ou privées qui offrent un traitement approprié pour les troubles mentaux en cause. Comme les cliniques psychiatriques ne sont pas toujours prêtes et à même de prendre en charge des patients peu coopératifs, le législateur a prévu que de telles mesures pouvaient également être exécutées au sein d'un établissement spécialisé d'exécution des mesures. Celui-ci doit être dirigé ou surveillé par un médecin; il faut en outre qu'il dispose des installations nécessaires ainsi que d'un personnel disposant d'une formation appropriée et placé sous surveillance médicale (arrêts 6B_384/2010 du 15 décembre 2010 consid. 2.1.1; 6B_629/2009 du 21 décembre 2009 consid. 1.2.1 et les références citées). Il ressort enfin de l'<ref-law> que les lieux d'exécution des mesures thérapeutiques visés aux art. 59 à 61 CP doivent être séparés des lieux d'exécution des peines.
L'<ref-law> prévoit que, tant qu'il existe un risque de fuite ou de récidive, le traitement doit être exécuté dans un établissement fermé; il peut aussi être effectué dans un établissement pénitentiaire au sens de l'<ref-law>, dans la mesure où le traitement thérapeutique nécessaire est assuré par du personnel qualifié (art. 59 al. 3 2 e phrase CP). En introduisant la possibilité d'exécuter une mesure institutionnelle dans un établissement pénitentiaire, le législateur a introduit une exception au principe de la séparation des lieux d'exécution des mesures de ceux d'exécution des peines (<ref-law>; arrêt 6B_629/2009 du 21 décembre 2009 consid. 1.2.2).
6.1.2. En application de l'<ref-law>, la mesure thérapeutique institutionnelle à laquelle le recourant est soumis depuis la décision du TAPEM du 24 avril 2009 peut être exécutée dans un établissement pénitentiaire. Comme il l'admet lui-même, il est suivi par du personnel qualifié. Sa détention ne peut ainsi pas être qualifiée d'illégale. Au surplus, s'il entendait remettre en cause la réalisation des conditions de l'<ref-law> permettant l'exécution d'une mesure en milieu fermé, il lui appartenait de recourir contre la décision du 24 avril 2009. Le délai de recours étant échu et cette décision n'étant pas entachée de nullité (supra consid. 5.4 et 5.5), il ne peut plus, dans le cadre de la présente procédure, remettre en cause cette décision. Son grief est infondé.
6.2. Le recourant soutient que sa détention depuis le 12 mars 2007 serait contraire aux art. 3 et 5 par. 1 CEDH et requiert une indemnisation à ce titre. Il reproche à la cour cantonale de n'avoir pas traité en fait et en droit l'argumentation présentée à cet égard.
6.2.1. Selon l'<ref-law>, les décisions qui peuvent faire l'objet d'un recours au Tribunal fédéral doivent indiquer « les motifs déterminants de fait et de droit » sur lesquels l'autorité s'est fondée. Si la décision attaquée ne satisfait pas à ces exigences, le Tribunal fédéral peut soit la renvoyer à l'autorité cantonale en invitant celle-ci à la parfaire, soit l'annuler (<ref-law>). Cette disposition concrétise le droit d'être entendu (art. 29 al. 2 Cst. et art. 6 par. 1 CEDH) dont la jurisprudence a déduit le devoir pour l'autorité de motiver sa décision, afin que le destinataire puisse la comprendre, la contester utilement s'il y a lieu et que l'autorité de recours puisse exercer son contrôle. Pour répondre à ces exigences, il suffit que le juge mentionne, au moins brièvement, les motifs qui l'ont guidé et sur lesquels il a fondé sa décision. Il n'a pas l'obligation d'exposer et de discuter tous les faits, moyens de preuve et griefs invoqués par les parties, mais peut au contraire se limiter à l'examen des questions décisives pour l'issue du litige (<ref-ruling> consid. 4.1 p. 88; <ref-ruling> consid. 3.3 p. 445). La motivation peut pour le reste être implicite et résulter des différents considérants de la décision (arrêt 6B_101/2011 du 14 février 2012 consid. 3.1).
6.2.2. La cour cantonale a indiqué que l'internement avait été prononcé par la Chambre d'accusation, conformément à la législation en vigueur, et le traitement institutionnel en milieu fermé par le TAPEM par un jugement entré en force qui n'avait pas été contesté. Elle en a conclu que les mesures ordonnées étaient parfaitement légales et par conséquent ne constituaient pas des mesures de contrainte illicites. Elle a ainsi refusé l'indemnisation requise (cf. arrêt p. 23).
6.2.3. La motivation cantonale apparaît insuffisante au regard des exigences exposées ci-dessus (consid. 6.2.1). En effet, elle n'examine pas les griefs relatifs à la violation des art. 3 et 5 CEDH et du droit cantonal genevois (en particulier l'art. 1 al. 1 et 3 RRIP/GE), pourtant soulevés par le recourant dans la procédure devant cette autorité (cf. mémoire du 21 février 2012 p. 27 ss). La cour cantonale n'a pas non plus établi les faits nécessaires à l'examen de ces griefs, plus particulièrement pour ce qui concerne les conditions de détention du recourant, les soins reçus en détention, l'éventuelle aggravation de son état de santé en détention, en considération notamment des différentes pièces invoquées par le recourant. Il n'est ainsi pas possible de vérifier le respect du droit conventionnel et l'éventuelle application arbitraire du droit cantonal. Il convient par conséquent d'annuler la décision attaquée et de renvoyer la cause à l'autorité précédente pour nouvelle instruction et nouvelle décision sur cet aspect.
A noter que l'<ref-law> invoqué par le recourant pour son indemnisation est sans portée. Selon cette disposition, le prévenu a droit à une indemnité ou à la réparation de son tort moral en cas de détention provisoire ou pour des motifs de sûreté lorsque celle-ci a excédé la durée autorisée et que la privation de liberté excessive ne peut être imputée sur les sanctions prononcées à raison d'autres infractions. Il ressort du texte même de cette disposition qu'elle s'applique à la détention provisoire ou pour des motifs de sûreté. Elle ne s'applique ainsi pas au cas du recourant qui exécute une mesure thérapeutique institutionnelle. L'indemnité invoquée par le recourant ne peut ainsi se fonder sur l'<ref-law>. Une éventuelle violation de la CEDH pourrait uniquement aboutir à une indemnisation fondée sur l'art. 5 par. 5 CEDH, point qu'il incombera à la cour cantonale de reprendre le cas échéant.
III. Conclusion et frais et dépens :
7.
Le recours de X._ doit être partiellement admis, l'arrêt attaqué annulé en ce qui concerne la question de la conformité des conditions de la détention de X._ au regard de la CEDH et du droit cantonal et celle de son éventuelle indemnisation. La cause sera renvoyée à la cour cantonale pour nouvelle instruction et nouvelle décision à cet égard. Pour le surplus, le recours de X._ est rejeté. Le recours du Ministère public est rejeté. Par conséquent, la mesure thérapeutique institutionnelle au sens de l'<ref-law> est confirmée, de même que son exécution, en l'état, en milieu ouvert.
8.
Le recourant a requis l'assistance judiciaire. Cette requête est sans objet dans la mesure où il obtient gain de cause et peut, à ce titre, prétendre à des dépens réduits de la part du canton (art. 64 al. 2 et 68 al. 1 LTF). Le recours était, pour le surplus, dénué de chance de succès, si bien que l'assistance judiciaire doit être refusée dans cette mesure (<ref-law>). Il peut être statué sans frais (art. 66 al. 1 et 4 LTF).
La requête d'effet suspensif est sans objet. Il y a lieu d'allouer des dépens réduits à l'intimé qui a été invité à se déterminer sur cette requête.

Par ces motifs, le Tribunal fédéral prononce:
1.
Les causes 6B_538/2013 et 6B_563/2013 sont jointes.
2.
Le recours du Ministère public est rejeté.
3.
Le recours de X._ est partiellement admis, l'arrêt attaqué annulé en ce qui concerne la question de la conformité des conditions de la détention de X._ au regard de la CEDH et du droit cantonal. La cause est renvoyée à la cour cantonale pour nouvelle instruction et nouvelle décision. Le recours est rejeté pour le surplus.
4.
Il n'est pas perçu de frais judiciaires.
5.
La demande d'assistance judiciaire de X._ est rejetée dans la mesure où elle n'est pas sans objet.
6.
Le canton de Genève versera à l'avocat de X._ une indemnité de 2000 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
7.
Le présent arrêt est communiqué aux parties et à la Cour de justice du canton de Genève, Chambre pénale d'appel et de révision.
Lausanne, le 14 octobre 2013
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Livet