Quelles sont les limites pratiques d'un langage complet non-turing comme Coq?

Question

Comme il y a des langues complètes non-turation là-bas, et étant donné que je n'ai pas étudié Comp Sci à l'université, quelqu'un pourrait expliquer quelque chose qu'un langage Turing-incomplet (comme Coq ) ne peut pas faire?

Ou est l'exhaustivité / incomplétude sans réelle pratique intérêt (ce qu'il ne fait pas beaucoup de différence dans la pratique)?

EDIT - Je suis à la recherche d'une réponse le long des lignes de vous ne pouvez pas construire une table de hachage dans un langage complet non-Turing en raison de X , ou quelque chose comme que!

Answer 1

D'abord, je suppose que vous avez déjà entendu parler de la Thèse de Church , qui stipule que tout ce que nous appelons « calcul » est quelque chose qui peut être fait avec une machine de Turing (ou l'un des nombreux autres modèles équivalents). Ainsi, un langage complet-Turing est celui dans lequel tout calcul peut être exprimé. A l'inverse, une langue Turing-incomplète est celle dans laquelle il y a un calcul qui ne peut être exprimé.

Ok, qui n'a pas été très instructif. Laissez-moi vous donner un exemple. Il y a une chose que vous ne pouvez pas le faire dans toutes les langues Turing-incomplet: vous ne pouvez pas écrire un simulateur de machine de Turing (sinon vous pouvez encoder tout calcul sur la machine de Turing simulé)

.

Ok, que toujours n'a pas été très instructif. la vraie question est, ce que utile programme ne peut pas être écrit dans un langage Turing-incomplet? Eh bien, personne est venu avec une définition de « programme utile » qui comprend tous les quelque part quelqu'un a écrit des programmes à des fins utiles, et qui ne comprend pas tous les calculs de la machine de Turing. Ainsi, la conception d'un langage Turing-incomplet dans lequel vous pouvez écrire tous les programmes utiles est encore un objectif de recherche très long terme.

Maintenant, il existe plusieurs types de langues Turing-incomplètes très différentes là-bas, et ils diffèrent en ce qu'ils ne peuvent pas faire. Cependant, il y a un thème commun. Si vous concevez une langue, il y a deux façons principales pour faire en sorte que la langue sera Turing-complet:

• exiger que la langue a des boucles arbitraires (while) et l'allocation de mémoire dynamique (malloc)

• exigent que les supports linguistiques arbitraires fonctions récursives

regard Let quelques exemples de langues complètes non Turing que certaines personnes pourraient néanmoins appeler les langages de programmation.

• Les premières versions de FORTRAN n'a pas eu allocation dynamique de mémoire. Il fallait comprendre à l'avance la quantité de mémoire de votre calcul aurait besoin et allouer cela. Malgré cela, FORTRAN était autrefois le plus largement utilisé le langage de programmation.

  La limitation pratique évidente est que vous devez prévoir les besoins en mémoire de votre programme avant de l'exécuter. Cela peut être difficile, et peut être impossible si la taille des données d'entrée ne sont pas limitée à l'avance. À l'époque, la personne alimentant les données d'entrée était souvent la personne qui avait écrit le programme, il n'a pas été un gros problème. Mais c'est tout simplement pas vrai pour la plupart des programmes écrits aujourd'hui.

• Coq est un langage conçu pour théorèmes prouvant . Maintenant prouvant théorèmes et des programmes en cours d'exécution sont très étroitement liés , de sorte que vous pouvez écrire des programmes en Coq juste comme vous prouvez un théorème. Intuitivement, une preuve du théorème « A implique B » est une fonction qui prend une preuve du théorème A comme argument et renvoie une démonstration du théorème B.

  Puisque le but du système est de démontrer des théorèmes, vous ne pouvez pas laisser l'écriture de programmation des fonctions arbitraires. Imaginez la langue que vous a permis d'écrire une fonction récursive stupide qui vient d'appeler lui-même (choisir la ligne qui utilise votre langue préférée):

  theorem_B boom (theorem_A a) { return boom(a); }
  let rec boom (a : theorem_A) : theorem_B = boom (a)
  def boom(a): boom(a)
  (define (boom a) (boom a))
  

  Vous ne pouvez pas laisser l'existence d'une telle fonction vous convaincre que A implique B, ou bien vous seriez en mesure de prouver quoi que ce soit et non pas seulement vrai théorèmes! Alors Coq (et démonstrateurs similaires) interdisent récursion arbitraire. Lorsque vous écrivez une fonction récursive, vous devez prouver qu'il a toujours termine , de sorte que chaque fois que vous exécutez sur une démonstration du théorème A vous qu'il construira une démonstration du théorème B.

  La limitation pratique immédiate de Coq est que vous ne pouvez pas écrire des fonctions récursives arbitraires. Étant donné que le système doit être en mesure de rejeter tous les nonfonctions -terminating, l'indécidabilité du problème (ou plus généralement langages de programmation synchrone sont langages conçus pour la programmation de systèmes en temps réel, c'est , les systèmes où le programme doit répondre en moins de n cycles d'horloge. Ils sont principalement utilisés pour les systèmes critiques tels que le contrôle des véhicules ou la signalisation. Ces langues offrent de solides garanties sur la durée d'un programme prendra pour exécuter et la quantité de mémoire peut affecter.

  Bien sûr, la contrepartie de ces garanties fortes est que vous ne pouvez pas écrire des programmes dont la consommation de mémoire et de temps en cours d'exécution, vous n'êtes pas en mesure de prévoir à l'avance. En particulier, vous ne pouvez pas écrire un programme dont la consommation mémoire ou durée dépend des données d'entrée.

• Il existe de nombreuses langues spécialisées qui ne tentent même pas d'être langages de programmation et ne peut donc rester confortablement loin d'être complet: les expressions régulières Turing, langages de données, la plupart des langages de balisage, ...

Par ailleurs, Douglas Hofstadter a écrit plusieurs livres de vulgarisation scientifique très intéressants sur le calcul, en particulier Braid Eternal Golden. Je ne me souviens pas s'il traite explicitement des limites de Turing incomplétude, mais la lecture de ses livres va certainement vous aider à comprendre des parties plus techniques.

Answer 2

La réponse la plus directe est: une machine / langue qui ne ne peut pas être Turing complet utilisé pour mettre en œuvre / simulent des machines de Turing. Cela vient de la définition de base de Turing-complet:. Une machine / langue Türing complète si elle peut mettre en œuvre / simulent les machines de Turing

Alors, quelles sont les implications pratiques? Eh bien, il y a une preuve que tout ce qui peut être démontré que turing complète peut résoudre tous les problèmes calculables. Ce qui par définition que tout ce qui est pas Türing complet a le handicap qu'il ya des problèmes calculables qu'il ne peut pas résoudre. Ce que ces problèmes sont dépend de quelles fonctionnalités sont manquantes qui rend le système complet non Turing.

Par exemple, si une langue ne prend pas en charge ou en boucle récursive ou implicitement boucles ne peuvent pas être complet parce que les machines de Turing peuvent Turing être programmés pour fonctionner à jamais. Par conséquent, cette langue ne peut pas résoudre des problèmes nécessitant des boucles.

Un autre exemple est si une langue ne prend pas en charge des listes ou des tableaux (ou vous permettre de les imiter par exemple en utilisant le système de fichiers), il ne peut pas mettre en œuvre une machine de Turing parce que les machines de Turing nécessitent un accès aléatoire arbitraire à la mémoire. Par conséquent, cette langue ne peut pas résoudre des problèmes nécessitant un accès aléatoire arbitraire à la mémoire.

Ainsi, la fonctionnalité qui manque qui classifie une langue pour être complète non-Turing est la chose qui limite l'utilité pratique de la langue. La réponse est, cela dépend: ce qui fait la complète langue non-Turing

Answer 3

Une classe importante de problèmes qui sont un mauvais ajustement pour les langues telles que Coq est ceux dont la terminaison est conjecturé ou difficile à prouver. Vous pouvez trouver beaucoup d'exemples dans la théorie des nombres, peut-être le plus célèbre est la conjecture Collatz

function collatz(n)
  while n > 1
    if n is odd then
      set n = 3n + 1
    else
      set n = n / 2
    endif
 endwhile

Cette limitation conduit à devoir exprimer ces problèmes d'une manière moins naturelle en Coq.

Answer 4

Vous ne pouvez pas écrire une fonction qui simule une machine de Turing. Vous pouvez écrire une fonction qui simule une machine de Turing pour 2^128 (ou étapes 2^2^2^2^128) et indique si la machine de Turing a accepté, rejeté ou RAN plus longtemps que le nombre autorisé d'étapes.

Depuis « dans la pratique », vous serez disparu depuis longtemps avant que votre ordinateur peut simuler une machine de Turing pour les étapes de 2^128, il est juste de dire que incomplétude Turing ne fait pas beaucoup de différence « dans la pratique ».