Se me ocurre necesidad de un algoritmo para una máquina de turing que lee una cadena de 0’s y, a continuación, escribe en la cinta cuántas personas había en binario.

Me doy cuenta de que en la práctica la máquina en realidad no contar el 0, pero yo estoy bastante confundido en cuanto a cómo hacerlo.

Me supongamos primero que todo me iba a necesitar para marcar el lugar donde el número binario se inicia con una X o algo, entonces acaba de escribir un 1 para el primer 0 y para cada uno de los siguientes 0s si el bit menos significativo es 0 se convierte en un 1, pero lo que si es un 1? Tal vez convertirlo en 0 y seguir a la izquierda de turing todos los 1s en 0s hasta que encuentre un 0 o en blanco para convertirse en 1? A continuación, de nuevo, en ese caso es lo mismo, independientemente de la LSB porque yo estaría haciendo lo mismo, sólo el 0 sería la primera posición…

Hmm…patito de goma…

  • Es esta tarea?
  • Se hacer necesidad de contar. La salida para el 8 de ceros es muy diferente de aquí para allá el uno para el 7, y no se puede saber cuántos hay hasta llegar al marcador final. De hecho, usted necesita un poco de memoria (un estado) para cada uno de los bits en la representación binaria de la cuenta.
  • No a la tarea, pero relacionadas con la universidad (que es un problema que me encontré mientras estudiaba) y el problema con el que cuenta es ¿cómo debo almacenar el contador?
  • Parece que tienes un algoritmo que funciona. ¿Cuál es el problema?

3 Comentarios

  1. 9

    Suponga que la entrada de la cinta es #00000000000#, donde la inicial de la lectura de la posición es el primer 0.

    1. Mover a la derecha hasta el final # es alcanzado, el mantenimiento de la paridad en el número de 0 encontrado (inicialmente, 0, 1, 0,…). Sustituir el primer 0 de cada par con un -. El - leer son ignorados y no de cambio de la paridad.

    2. Escribir la paridad a la salida de la cinta y se mueve a la izquierda (para escribir los bits en orden)

    3. Devolver la entrada de la cabeza a la izquierda #, y goto 1.

    Al final de la primera pasada, la entrada de la cinta será #-0-0-0-0-0-# y la salida es 1.

    Al final de la segunda pasada: #---0---0---# y 11.

    Al final de la tercer paso: #-------0---# y 011.

    Al final del cuarto paso: #-----------# y 1011.

    • Si lo entiendo correctamente, que, básicamente, se divide por dos y redondee hacia abajo en cada paso?
    • Sí, exactamente. Sustitución de la antes 0, se redondeará hacia abajo correctamente en todos los casos.
  2. 0

    Echa un vistazo a este simulador de máquina de Turing y su numeración binario programa de ejemplo:

    Uber Máquina De Turing permite
    programa de la máquina de Turing – un
    universal teórico dispositivo que puede
    ser adaptado para simular la lógica de cualquier
    algoritmo de computadora. Con la ayuda de
    este software es capaz de crear
    nuevos algoritmos, así como editar
    ya preparados por alguien a través de
    la apertura y la alteración de los mismos a través de
    conveniente visual IDE.

    Máquina de Turing algoritmo de conteo 0 y escribe cuántos hay en binario

  3. 0

    Edición: reconozco a Bainville.

    Me di cuenta de lo que quería hacer ayer por la noche y es necesario separar los dos máquinas de turing y eso es probablemente la trampa.

    La primera máquina de la cabeza se ejecuta a través de la entrada de la cinta y simplemente el inicio de la segunda máquina si se escanea un 0.

    La segunda máquina es simplemente una máquina de sumar y habría que añadir un 1 al número actual, que es bastante fácil de hacer, es sólo el tiempo, además de crear un estado que dice que hay un resto y seguir avanzando a la izquierda hasta llegar a cero (y reemplazarlo con 1) o encontrar un punto en blanco (y crear un 1).

    Bainville gana mi voto.

Dejar respuesta

Please enter your comment!
Please enter your name here