2010-04-15 18 views
3

Je travaille sur un projet de machine à tourner mais j'ai du mal à conceptualiser les étapes.Comment créer une machine de Turing qui prend un nombre décimal à un chiffre de 0 à 9 et sort le cube

f(x) = x^3, where x is a single digit between 0 - 9 inclusive. 

Sur la base de ma compréhension, je dois convertir le nombre en binaire, mais comment puis-je trouver le cube d'un nombre en binaire.

De même, comment écrire le cube sur la bande. Jusqu'à présent, je pense que je devrais créer un diagramme d'état qui accepte les versions binaires de 0-9 mais que faire ensuite?

+0

Je commence à m'interroger sur le "chiffre unique" - est-ce que cette machine de Turing peut écrire les symboles 0-9 (plus blanc)? Cela rendrait cela beaucoup plus faisable. En binaire (ou pire, unaire) c'est une tonne de travail inutile. –

+0

C'était mon approche exacte à l'origine, mais quand j'ai pris la conception au tuteur, elle a dit que la machine de Turing ne peut traiter qu'avec binaire. :-( – Julian

Répondre

2

je le ferais comme ceci:

  • Ecrivez une copie du numéro à gauche de votre numéro actuel
  • Ecrire une autre copie à gauche de cette
  • Multiplier le numéro initial première copie, l'effacement de la copie
  • Multiplier le résultat par la deuxième copie, l'effacement que

Vous devrez WRI te une copie et une multiplication de "sous-programme" (en utilisant des états) et saute dedans en établissant les bons états. Mais je pense que cela devrait être faisable (si beaucoup de travail). Mais probablement moins de travail que d'encoder tous les cubes de 0 à 9.

+0

Comment puis-je écrire une copie? Pour autant que je sache, la transition pour une machine à écrire est généralement sous la forme {0, 1 -> R} {où vous lisez dans un chiffre, le remplacer par autre chose et passer à autre chose.} Puis-je écrire deux chiffres, par exemple {0, 11 -> R}? – Julian

+0

Non. Je pense que vous devez lire le chiffre, le mémoriser dans l'état, trouver la fin de la copie et l'ajouter . –