search

comp-think / 2021-2022

The GitHub repository containing all the material related to the Computational Thinking and Programming course of the Digital Humanities and Digital Knowledge degree at the University of Bologna (a.a. 2021/2022).
17 stars 9 forks source link

Lecture "Computability", exercise 1 #8

Open essepuntato opened 2 years ago

essepuntato commented 2 years ago

Write the table of instructions of a Turing machine with four states – A (initial state), B, C, and D (final state) – such that, once reached the final state, only the cells immediately on the left and on the right of the initial position of the head of the machine will have the value 1 specified. The final state must not have any instruction set in the table.

ghasempouri1984 commented 2 years ago 
input: ' '
blank: '0'
start state: A
table:
  A:
    ' ' : { write: 0, R: B}
    0  : { write: 0, L: C}
  B:
    0 : { write: 1, L: A }
  C:
    0 : { write: 1, R: D }
  D:
Veronicaonofri commented 2 years ago

WhatsApp Image 2021-10-20 at 16 58 19

LudovicaErre commented 2 years ago

IMG_20211020_200104

ManueleVeggi commented 2 years ago

I attach my solution proposal for this exercise:

Current State Tape Symbol Write Symbol Move Head New State
A 0 1 Right B
B 0 1 Left A
A 1 0 Left C
C 0 1 Right D

On "Turing machine Visualization" this can be rendered as: 

blank: '0'
start state: A
table:
  A:
    0: {write: 1, R: B}
    1: {write: 0, L: C} 
  B:
    0: {write: 1, L: A}
  C:
    0: {write: 1, R: D}
  D:
Schermata 2021-10-21 alle 00 48 56
Bianca-LM commented 2 years ago

Current stateTape symbol_Write symbolMove head__Next state A_____read 0 or 1____0leftB B____read 0 or 1____1__right__C__ C_read 0 or 1____0__right__B__ B_read 0 or 1____1__right__D__

CarmenSantaniello commented 2 years ago

IMG_20211021_110742

olgagolgan commented 2 years ago

IMG_0024

tommasobattisti commented 2 years ago

Table of instructions:

<html xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">

CURRENT STATE | TAPE SYMBOL | WRITE SYMBOL | MOVE HEAD | NEW STATE -- | -- | -- | -- | -- A | 0 | 1 | Left | B A | 1 | 0 | Right | C B | 0 or 1 | 1 | Right | A C | 0 or 1 | 1 | Left | D

On "Turing machine visualization":

Schermata 2021-10-21 alle 17 02 04 Schermata 2021-10-21 alle 15 26 40
martasoricetti commented 2 years ago

ex1-computability

giorgimariachiara commented 2 years ago

Current state | Tape symbol | Write symbol | Move head | Next state

A | 0 | 1 | right | B A | 1 | 0 | left | C B | 0 | 1 | left | A C | 0 | 1 | left | D

angstigone commented 2 years ago
Schermata 2021-10-21 alle 16 02 29 Schermata 2021-10-21 alle 16 02 57
sarabecchi commented 2 years ago

esercizio

OrsolaMBorrini commented 2 years ago

Schermata 2021-10-22 alle 10 55 34 I found it much easier to understand using the Turing machine visualization. I don't think it is the case, but I was wondering if the order of the instructions within the table is of any importance or not... Schermata 2021-10-22 alle 10 57 32

victorchaix commented 2 years ago

Capture d’écran 2021-10-22 à 11 52 58 AM

lelax commented 2 years ago

Turing01

AmeliaLamargese commented 2 years ago

es 1

In the initial state A, the symbol on the tape is 0 by default, so the instruction says to write 1 on the cell of the initial position and move left. Now we can fill the cell on the immediate left of the initial position with the digit 1; indeed, we will pass to the state B, which says to write 1 and move right, so we will be again on the initial position. With the current state set on A, this time the symbol on the tape is 1, so the instruction of the state A says to write a 0 and then move right, in order to fill the cell on the immediate right of the initial position and, according to the state C, we will write 1 and move right to the final state D. In the end, we will have the digit 1 just inside the cells to the immediate left and right of the initial position.

sanyuezoe commented 2 years ago

Firefox_Screenshot_2021-10-30T07-20-44 831Z

Postitisnt commented 2 years ago

image