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.