Y a-t-il des problèmes spécifiques connus pour être indécidables pour des raisons autres que la diagonalisation, l'auto-référence ou la réductibilité?

28

Chaque problème indécidable que je connais tombe dans l'une des catégories suivantes:

  1. Problèmes indécidables en raison de la diagonalisation (auto-référence indirecte). Ces problèmes, comme le problème d'arrêt, sont indécidables car vous pourriez utiliser un prétendu décideur pour le langage pour construire une MT dont le comportement conduit à une contradiction. Vous pourriez également regrouper de nombreux problèmes indécidables concernant la complexité de Kolmogorov dans ce camp.

  2. Problèmes indécidables dus à l'auto-référence directe. Par exemple, le langage universel peut être démontré comme indécidable pour la raison suivante: s'il était décidable, alors il serait possible d'utiliser le théorème de récursivité de Kleene pour construire une MT qui obtient son propre encodage, demandez s'il acceptera sa propre entrée , fait alors le contraire.

  3. Problèmes indécidables en raison des réductions des problèmes indécidables existants. De bons exemples ici incluent le problème de correspondance postérieure (réduction du problème d'arrêt) et le problème Entscheidungs.

Lorsque j'enseigne la théorie de la calculabilité à mes étudiants, de nombreux étudiants s'en rendent compte également et me demandent souvent s'il y a des problèmes que nous pouvons prouver comme indécidables sans finalement remonter à une sorte de ruse d'auto-référence. Je peux prouver de manière non constructive qu'il existe une infinité de problèmes indécidables par un simple argument de cardinalité reliant le nombre de MT au nombre de langues, mais cela ne donne pas un exemple spécifique de langage indécidable.

Existe-t-il des langues indécidables pour des raisons qui ne sont pas répertoriées ci-dessus? Si oui, quelles sont-elles et quelles techniques ont été utilisées pour montrer leur indécidabilité?

computability proof-techniques undecidability templatetypedef
la source
@EvilJS Ma compréhension était que la preuve de l'indécidabilité impliquait la possibilité de simuler des MT, bien que je me trompe peut-être?
templatetypedef
Vous pouvez dire que le théorème de Rice ne rentre dans aucune de ces catégories, mais la preuve du théorème le fait.
Ryan
1
@EvilJS C'est un bon point. Vraiment, ce que je recherche ici, c'est s'il existe une technique fondamentalement différente que nous pouvons utiliser. Ce serait bien, par exemple, si quelqu'un identifiait un problème comme indécidable dans un cas où ce problème n'avait aucune relation connue avec l'auto-référence TM ou un argument de type Godeling. Si le mieux que nous puissions faire est "nous avons compris celui-ci il y a longtemps, puis nous avons réalisé qu'il est plus facile de le prouver d'une autre manière", cela serait en quelque sorte une réponse - les trois techniques ci-dessus représentent fondamentalement toutes les preuves de indécidabilité que nous connaissons.
templatetypedef
2
La fonction de castor occupé se développe trop rapidement pour qu'un programme puisse le calculer. Concrètement, vous pouvez définir une fonction comme une plus le plus grand nombre calculé par un programme de longueur au plus . Est-ce que cela compte comme diagonalisation? nf(n)n
Yuval Filmus
1
@YuvalFilmus Peut-être que je suis trop strict ici, mais cela ressemble à un argument de type diagonal pour moi: vous construisez une fonction qui est définie pour être différente de toutes les fonctions calculées par les MT.
templatetypedef

Réponses:

10

Oui, il existe de telles preuves. Ils sont basés sur le théorème des bases basses .

Voir cette réponse à Y a-t-il des preuves de l'indécidabilité du problème d'arrêt qui ne dépend pas de l'auto-référencement ou de la diagonalisation? question sur cstheory pour plus.

Kaveh
la source
Si quelqu'un s'intéresse aux techniques avancées de la théorie de la calculabilité, consultez les livres de Robert I. Soare sur les ensembles et degrés énumérables récursifs et la théorie et les applications de la calculabilité .
Kaveh
Corrigez-moi si je me trompe, mais la preuve du théorème de base faible ne consiste-t-elle pas à appliquer une fonctionnelle à elle-même et à se demander si elle ne produit pas de valeur? Si oui, n'est-ce pas juste une couche d'indirection au-dessus d'un argument diagonal?
templatetypedef
@templatetypedef, je ne suis pas un expert mais pour autant que je comprends non. Voir par exemple la page 109 du livre de Soare.
Kaveh
@templatetypedef, ps1: il y a un certain flou dans la question de ce que nous considérons comme la diagonalisation. Si nous ne faisons pas attention, nous pouvons étendre ce que nous considérons comme la diagonalisation chaque fois que nous voyons quelque chose qui ne l'était pas. Prenons par exemple les méthodes prioritaires ou toute méthode générale de construction d'objets partie par partie de manière à éviter d'être égal à tout objet d'une classe donnée.
Kaveh
2
@David, :) J'ouvre la page du livre que je veux partager, je clique sur le bouton de partage en haut et je supprime les paramètres sauf le idet pgdu lien.
Kaveh
0

ce n'est pas exactement une réponse affirmative, mais une tentative de quelque chose de proche de ce qui est demandé via un angle créatif. il y a maintenant pas mal de problèmes en physique qui sont "très éloignés" des formulations mathématiques / théoriques d'indécidabilité, et ils semblent de plus en plus "éloignés" des "formulations originales impliquant le problème d'arrêt, etc." et "ne ressemblent guère à". bien sûr, ils utilisent le problème de l'arrêt à la racine, mais les chaînes de raisonnement sont devenues de plus en plus distantes et ont également un aspect / une nature "appliquée" forte. malheureusement, il ne semble pas encore y avoir de grandes enquêtes dans ce domaine. un problème récent qui s'est révélé "étonnamment" indécidable en physique et qui a attiré beaucoup d'attention:

L'écart spectral - la différence d'énergie entre l'état fondamental et le premier état excité d'un système - est au cœur de la physique quantique à plusieurs corps. De nombreux problèmes ouverts difficiles, tels que la conjecture de Haldane, la question de l'existence de phases liquides de spin topologiques espacées et la conjecture de l'écart de Yang – Mills, concernent les écarts spectraux. Ces problèmes et d'autres sont des cas particuliers du problème général de l'écart spectral: étant donné l'hamiltonien d'un système quantique à plusieurs corps, est-il lacunaire ou sans espace? Ici, nous prouvons qu'il s'agit d'un problème indécidable. Plus précisément, nous construisons des familles de systèmes de spin quantique sur un réseau bidimensionnel avec des interactions translationnellement invariantes, le plus proche voisin, pour lesquelles le problème de l'écart spectral est indécidable. Ce résultat s'étend à l'indécidabilité d'autres propriétés à faible énergie,

ce que vous semblez observer dans la question, c'est que les preuves d'indécidabilité (informelles) ont toutes une certaine structure "autoréférentielle", et cela a été formellement prouvé dans des mathématiques encore plus avancées, de sorte que le problème d'arrêt de Turing et le théorème de Godels peuvent être considérés comme des exemples du même phénomène sous-jacent. voir par exemple:

Le théorème d'arrêt, le théorème de Cantor (le non-isomorphisme d'un ensemble et de son ensemble de pouvoirs) et le théorème d'incomplétude de Goedel sont tous des exemples du théorème du point fixe de Lawvere, qui dit que pour toute catégorie fermée cartésienne, s'il existe une carte épimorphique e: A → (A⇒B) alors chaque f: B → B a un point fixe.

il y a aussi une longue méditation sur ce thème de l'interconnectivité (intrinsèque?) de l'autoréférentialité et de l'indécidabilité dans les livres de Hofstadter. un autre domaine où les résultats de l'indécidabilité sont courants et étaient initialement quelque peu «surprenants» est celui des phénomènes fractals. l'apparence / signification transversale de phénomènes indécidables à travers la nature est presque un principe physique reconnu à ce stade, observé pour la première fois par Wolfram comme "principe d'équivalence informatique" .

vzn
la source
autres domaines d'indécidabilité "surprenants / appliqués": pavages apériodiques , stabilisation éventuelle dans conway game of Life ( automates cellulaires )
vzn
3
Je crois comprendre que les preuves que tous ces problèmes sont indécidables se résument toutes à des réductions du problème de l’arrêt. Est-ce que c'est incorrect?
templatetypedef
la réponse concède essentiellement que (tous les résultats connus d'indécidabilité peuvent être réduits au problème d'arrêt). votre question est presque formulée comme une conjecture, et je n'ai connaissance d'aucune connaissance contradictoire, et je vois beaucoup de preuves circonstancielles en sa faveur. mais le plus proche d'une preuve formelle connue est apparemment les formulations à virgule fixe de l'indécidabilité (il ne semble pas y avoir d'autres formulations formelles d '"autoréférentiel"). essentiellement du même phénomène.
vzn