Est-ce branchement conditionnel une exigence de Turing-complet?

Question

J'ai recherche sur le Web et je trouve des réponses quelque peu contradictoires. Certaines sources affirment qu'une langue / la machine / ce-have-vous est Türing complet si et seulement si elle a deux branchement conditionnel et inconditionnel (que je suppose est une sorte de redondance), certains disent que seulement inconditionnel est nécessaire, d'autres qui ne sont nécessaires sous condition.

Lecture sur l'allemand Z3 et ENIAC , Wikipedia dit:

  

L'Allemand Z3 (montré de travailler en mai   1941) a été conçu par Konrad Zuse. Il   a été le premier numérique à usage général   ordinateur, mais il était   électromécanique, plutôt que   électronique, utilisé comme relais pour tous   les fonctions. Il calculé logiquement à l'aide   mathématiques binaires. Il est programmable par   bande perforée, mais il manquait la   branchement conditionnel. Sans conçu   pour Turing complet, il   accidentellement était, comme il a été constaté   en 1998 (mais pour exploiter cette   Turing-complet, complexe, intelligent   hacks étaient nécessaires).

Ce complexe, hacks intelligent, exactement?

1998 Résumé papier par R. Rojas précise également (Notez que je n'ai pas lu cet article, il est juste un extrait de l'IEEE.):

  

La machine de calcul Z3, construit par   Konrad Zuse entre 1938 et 1941,   pourrait exécuter des séquences seulement fixes   virgule flottante opérations arithmétiques   (addition soustraction,   multiplication, division et carré   root) codée dans une bande perforée. Un   question intéressante à poser, de la   point de vue de l'histoire de l'informatique,   est de savoir si ces opérations sont ou non   suffisante pour le calcul universel.   Les émissions de papier qui, en fait,   seule boucle de programme contenant ceux-ci   instructions arithmétiques peuvent simuler   une machine de Turing dont la bande est d'une   étant donné la taille finie. Cela se fait par   simulant le branchement conditionnel et   adressage indirect par purement   des moyens arithmétiques. Z3 Zuse est   Par conséquent, au moins en principe, comme   universel que les ordinateurs d'aujourd'hui que   disposer d'un espace d'adressage borné.

En bref, Soers, quel type de ramification est exactement requis pour Turing complet? En supposant que la mémoire infinie, une langue peut avec seulement une construction de branchement goto ou jmp (pas de constructions if ou jnz) être considérés comme Turing-complet?

Answer 1

Le papier Rojas original se trouve ici . L'idée de base est que le Z3 ne supporte qu'une seule boucle inconditionnelle (par collage des extrémités de la bande d'instruction en même temps). Vous construire l'exécution conditionnelle de celui-ci en mettant toutes les sections de code les uns après les autres dans la boucle, et ayant une variable z qui détermine la section à exécuter. Au début de la section j, vous définissez

 if (z==j) then t=0 else t=1

et ensuite faire chaque a = b op c d'affectation dans cette section lu

 a = a*t + (b op c)*(1-t)

(i.e.. Chaque affectation est une no-op, sauf dans la partie active). Maintenant, cela inclut encore une affectation conditionnelle: comment comparer z == j? Il propose d'utiliser la représentation binaire de z (z1..zm), ainsi que la représentation binaire inversé de j (c1..cm), puis calculer

t = 1 - sqr((c1-z1)(c2-z2)...(cm-zm))

Ce produit sera 1 seulement si c et z sont différents dans tous les bits, ce qui ne se produira que si z == j. Une affectation à z (qui est essentiellement un saut indirect) doit également affecter à z1..zm.

Rojas a également écrit conditionnelle Branching n'est pas nécessaire pour le calcul universel de von Neumann dans les ordinateurs . Là, il propose une machine avec le code d'auto-modification et l'adressage relatif, de sorte que vous pouvez lire les instructions de la mémoire de Turing, et de modifier le programme de sauter en conséquence. Comme alternative, il propose l'approche ci-dessus (pour Z3), dans une version qui utilise uniquement LOAD (A), MAGASIN (A), INC et DEC.

Answer 2

Si vous avez seulement des expressions arithmétiques vous pouvez utiliser certaines propriétés des opérations arithmétiques. Par exemple, est A est 0 ou 1 en fonction de certaines conditions (qui est calculé précédemment), puis A*B+(1-A)*C calcule l'expression if A then B else C.

Answer 3

Vous avez besoin quelque chose qui peut se ramifier en fonction des résultats (de) entrée.

Une façon de Simuler branches conditionnelles est avec le code automodifiant - vous faites un calcul qui dépose son résultat dans le flux d'instructions en cours d'exécution. Vous pouvez mettre l'op-code pour un saut inconditionnel dans le flux d'instructions, et faire des mathématiques sur une entrée pour créer la bonne cible pour ce saut, selon un certain ensemble de conditions pour l'entrée. Par exemple, il faut soustraire x de y, droit de passage à 0 remplissage si elle est positive ou 1 remplissage si elle était négative, puis ajoutez une adresse de base, et stocker ce résultat immédiatement après l'op-code JMP. Lorsque vous arrivez à JMP, vous allez à une adresse si des X y, et un autre si x! = Y.

Answer 4

Si vous pouvez calculer l'adresse de votre goto ou jmp, vous pouvez simuler conditionals arbritary. Je parfois utilisé pour simuler ce "ON x GOTO a, b, c" ZX Basic.

Si "true" a la valeur numérique 1 et "false" 0, une construction comme:

if A then goto B else goto C

est identique à:

goto C+(B-C)*A

Alors, oui, avec un « goto calculé » ou la capacité d'auto-modifier, ou un goto JMP peut agir en tant que sous condition.

Answer 5

Le Z3 ne fut complète d'un Turing point de vue abstrait. Vous pouvez avoir une bande de programme arbitraire de long et ont juste calculer les deux côtés de chaque branche conditionnelle. En d'autres termes, pour chaque branche, il calcule les réponses et vous dire que l'on ignorer. Il est évident que cela crée des programmes exponentiellement plus pour chaque branchement conditionnel vous auriez, vous pourriez ne jamais utiliser cette machine de manière Turing-complet.

Answer 6

Vous n'avez pas besoin branchement conditionnel pour construire une machine complète-Turing, mais bien sûr, toute machine complète Turing-fournirez branchement conditionnel comme une caractéristique de base.

Il a été prouvé que les systèmes aussi simple que Règle 110 Cellular Automaton peuvent être utilisés pour mettre en œuvre une machine de Turing. Vous ne vous avez pas besoin de tirer branchement conditionnel d'un tel système du seau bits. En fait, on pourrait simplement utiliser un tas de roches .

Le point est qu'une machine de Turing fournira le branchement conditionnel, donc ce que vous faites de toute façon en prouvant Turing-complet est un peu en œuvre branchement conditionnel. Vous devez le faire sans branchement conditionnel à un moment donné, que ce soit des roches ou des jonctions PN dans les semi-conducteurs.

Answer 7

Si une machine peut se ramifier, alors oui il est considéré comme complet Turing.

La raison est d'avoir conditionnel Le branchement permet automatiquement un ordinateur complet Turing. Cependant, il y a aussi des machines qui ne peuvent pas sauter branche ou même si, mais sont toujours considérés comme Turing complet.

Le traitement est tout simplement le processus d'identification des entrées dans l'ordre pour sélectionner les sorties.

Branching est une façon de mentalisation ce processus, la condition du saut est ce qui peut classer les entrées, l'endroit où vous branche en magasins la sortie correcte pour cette entrée.

Enfin, pour clarifier les choses:

Si vous avez branchement conditionnel votre ordinateur est nécessairement équivalent à informatiquement une machine de Turing. Cependant, il y a beaucoup d'autres façons pour un ordinateur pour réaliser Turing-complet (lambda, IF de, CL).