Après avoir lu une question connexe , sur les preuves d'existence d'algorithmes non constructives, je me demandais s'il existe des méthodes pour montrer l'existence de "petites" machines de calcul (disons, par état) sans les construire. Officiellement: supposons qu'on nous donne un langage et...
Je recherche un petit langage qui aide à «convaincre» les étudiants que les machines de turing sont un modèle informatique suffisamment général. Autrement dit, un langage qui ressemble aux langues auxquelles ils sont habitués, mais qui est également facile à simuler sur une machine de turing....
Réponse: inconnue Un grand merci à tous ceux qui ont contribué à affiner cette question et les définitions qui y sont associées. Les définitions de ce wiki ont fourni le point de départ du plus récent wiki TCS " P contient-il des langues dont l'existence est indépendante de PA ou ZFC? (Wiki...
Robin Gandy était un étudiant d' Alan Turing . Gandy a fait une analyse du moteur analytique de Babbage (voir 'Gandy - The Confluence of Ideas in 1936' cité dans 'Herken, Rolf - The Universal Turing Machine - A Half-Century Survey . Springer Verlag') - et l'a dit (cf. p. 52-53): Les fonctions...
Pour célébrer l'anniversaire d'Alan Turing, Google a publié un doodle montrant une machine. Quel type de machine est le doodle? Peut-il exprimer une langue Turing Complete? Il existe des différences évidentes avec la machine de turing classique: une bande finie, des contraintes dans la façon dont...
Je suis un étudiant en master axé sur les systèmes distribués mais également intéressé par l'informatique théorique. Je me demandais s'il y avait une représentation formelle d'un système distribué au-dessus d'une machine de turing? Autrement dit, est-il possible d'étendre (faire une variante) le...
Je jouais avec la question très intéressante et toujours ouverte " Alphabet of single-tape Turing machine " (par Emanuele Viola) et j'ai trouvé la langue suivante: L = { x ∈ { 0 , 1 }n st | x | = n = 2m et c o u n t 1 ( x ) = k ∗ m ;n , m , k ≥ 1
La plupart de la littérature semble s'intéresser aux machines à oracles simples pour des problèmes spécifiques, mais il semble y avoir quelques articles qui considèrent les machines à oracles multiples. Existe-t-il un bon article ou une thèse qui donne un aperçu de ce que l'on sait de ces machines?...
Les automates bornés linéaires non déterministes à visite bornée ne reconnaissent-ils que les langues régulières? Par un automate borné linéaire non déterministe (nLBA), je veux dire une machine de Turing non déterministe à bande unique où l'entrée est "rembourrée" avec des marqueurs de fin aux...
Fixons un encodage des machines de Turing et une machine de Turing universelle, U, qui en entrée (T, x) sort quelles que soient les sorties T en entrée x (éventuellement les deux fonctionnant pour toujours). Définissez la complexité de Kolmogorov de x, K (x), comme la longueur du programme le plus...
Depuis un certain temps, je suis curieux de voir les machines de Turing avec exactement une bande et exactement 3 états (à savoir l'état de démarrage , l'état d'acceptation et l'état de rejetq0q0q_0qacceptqacceptq_{accept}qrejectqrejectq_{reject} ). Notez que j'autorise les alphabets de bande...
J'ai une question naïve: existe-t-il une machine de Turing dont la terminaison est vraie mais non démontrable par aucune théorie naturelle, cohérente et finement axiomatisable? Je demande une simple preuve d'existence plutôt qu'un exemple spécifique. Cela pourrait avoir un lien avec l'analyse...