Machine de Turing algorithme pour compter de 0 et écrire combien il y en avait en binaire

J'ai besoin d'un algorithme pour une machine de turing qui lit une chaîne de 0 et de l'écrit sur la bande combien il y en avait en binaire.

Je me rends compte que, dans la pratique, la machine ne fait pas de compter le 0 mais je suis assez perplexe quant à la façon de le faire.

Je supose tout d'abord, j'avais besoin de marquer l'endroit où le nombre binaire commence par un X ou quelque chose, alors il suffit d'écrire un 1 pour le premier 0 et pour chacun des éléments suivants, 0 si le bit le moins significatif est un 0, il devient un 1 mais si c'est un 1? Peut-être le transformer en 0, et continuez à gauche de turing tous les 1 à 0 jusqu'à ce que je trouve un 0 ou vide à son tour en 1? Puis à nouveau, dans ce cas, c'est la même chose quel que soit le LSB parce que je ferais la même, seuls les 0 serait la première position...

Hmm...duckie en caoutchouc...

Est-ce devoirs?
Vous ne besoin de compter. La sortie de 8 zéros est très différent bof l'un pour 7, et vous ne pouvez pas savoir combien il y en a jusqu'à ce que vous atteignez la fin d'un marqueur. En fait, vous avez besoin d'un peu de mémoire (un état) pour chacun des bits de la représentation binaire du comte.
Pas de devoirs, mais au collège (c'est un problème que j'ai croisé pendant ses études), et le problème avec le comptage est de savoir comment dois-je stocker le compteur?
Vous semblez avoir un algorithme qui fonctionne. Quel est le problème?

OriginalL'auteur João Fernandes | 2011-01-11

  1. 9

    Supposons que l'entrée de bande est #00000000000#, où la première position de lecture est le premier 0.

    1. Déplacer vers la droite jusqu'à la fin # est atteint, le maintien de la parité du nombre de 0 rencontrés (initialement 0, puis 1, puis 0,...). Remplacer la première 0 de chaque paire avec un -. Le - lire sont ignorés et ne changez pas la parité.

    2. Écrire la parité à la sortie de la bande et se déplacer vers la gauche (pour écrire les bits dans l'ordre)

    3. Retour à l'entrée de la tête vers la gauche #, et goto 1.

    À la fin de la première passe, l'entrée de bande sera #-0-0-0-0-0-# et de sortie est 1.

    À la fin de la deuxième passe: #---0---0---# et 11.

    À la fin de la troisième passe: #-------0---# et 011.

    À la fin de la quatrième phase: #-----------# et 1011.

    Si je comprends bien, en gros, vous divisez par deux et arrondi à l'inférieur sur chaque passage?
    Oui, exactement. Remplacement de la premier 0 arrondir correctement dans tous les cas.

    OriginalL'auteur Eric Bainville

  2. 0

    Découvrez cette machine de Turing simulateur et son calcul binaire exemple de programme:

    Uber Machine De Turing vous permet de
    programme de la machine de Turing - un
    universel théorique de l'appareil qui peut
    être adaptés pour simuler la logique de toutes les
    algorithme informatique. Avec l'aide de
    ce logiciel vous êtes en mesure de créer
    de nouveaux algorithmes, ainsi que de modifier
    déjà préparé par quelqu'un à travers
    l'ouverture et la modification de via la
    pratique de visual IDE.

    Machine de Turing algorithme pour compter de 0 et écrire combien il y en avait en binaire

    OriginalL'auteur Dmitry Kramarov

  3. 0

    Edit: je concède à Bainville.

    J'ai compris ce que je voulais faire la nuit dernière et il a fallu deux machines de turing et c'est probablement en train de tricher.

    La première machine de la tête devrait être de plus de l'entrée de bande et simplement commencer la deuxième machine si elle scanné un 0.

    La deuxième machine serait tout simplement une machine à additionner et permettrait d'ajouter 1 au nombre actuel, qui est assez facile à faire, c'est juste plus long et vous pouvez créer un état qui dit qu'il y a un reste et continuer à aller de gauche jusqu'à atteindre une valeur de zéro (et le remplacer par 1) ou trouver un endroit vide (et de créer un 1).

    Bainville gagne mon vote.

    OriginalL'auteur ptpaterson