Lecture "Computability", exercise 1

[essepuntato]

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.

[CarlaMenegat]

[vattelalberto]

I managed to design a turing machine that works if the input is fixed (0) but could not design one working for any input number with only 4 nodes.
This is my turingmachine.io code:

blank: '0'
start state: A
end state: D
table:
  A:
    '0' : {write: 1, R: B}
    '1'  : {write: 0, L: C}
  B:
    [0, 1] : {write: 1, L: A}
  C:
    [0, 1] : {write: 1, R: D}
  D:

[Liber-R]

[Asemica-me]

blank: '0' 
start state: A 
table: 
  A:
    0: { write: 1, L: B } 
    1: { write: 0, R: C }
  B:
    0: { write: 1, R: A }
  C:
    0: { write: 1, R: D }
  D:

[rufferbaraldi]

input: '000'
blank: '0'
start state: A
end state: D
table:

A:
[0, 1] : {write: 1, R: B}
B:
[0, 1] : {write: 0, R: C}
C:
[0, 1] : {write: 1, L: D}
D:

[qwindici]

blank: '0'
start state: A
table:

  A:
    0: {write: 1, L: B}
  B: 
    1: {write: 0, R: C}
    0: {write: 1, R}
  C:
    0: {write: 1, L: D}
  D:

[rufferbaraldi]

Correcting...

[parkful]

98bbc8">

[valetedd]

table:
  A:
    [0, 1, ' ']: {write: '0', L: B}
  B:
    " ": {write: 1, R: B}
    0: {R: C}
    1: {write: 0, R: C}
  C:
    " ": {write: 1, L: D}
  D: ```

[valentinabertelli]

blank: " "
start state: A
table:
A:
0: {L: C}
1: {L: C}
" ": {write: 0, R: B}
B:
0: {write: 1, L: A}
1: {write: 1, L: A}
" ": {write: 1, L: A}
C:
0: {write: 1, L: D}
1: {write: 1, L: D}
" ": {write: 1, L: D}
D:

[VirginiaDa00]

[essepuntato]

Hi all, thanks for your takes. Just a note for all: remember that you are entitled to use only two symbols in the Turing Machines, i.e. 0 and 1, so the blank symbol should be 0. Using, as a blank symbol, the space character means to use three symbols in the Turing Machine...

[frammenti]

Start state: A
End state: D

Current state	Tape symbol	Write symbol	Move head	Next state
A	0	1	L	B
B	0	1	R	C
C	1	0	R	B
C	0		R	D
D

# 1 is printed only left and right the starting position.
blank: '0'
start state: A
table:
  # print 1, move left
  A:
    [0]: {write: 1, L: B}
  # print 1, move back right
  B:
    [0]: {write: 1, R: C}
  # check if 1, turn it to 0 and back to B, otherwise stop
  C:
    [1]: {write: 0, R: B}
    [0]: {R: D}
  D:

[saramadonia]

[annapasetto0]

input: '00000'
blank: '0'
start state: A
table:
A:
0: {write: 1, L: B}
1: {write: 0, R: C}
B:
0: {write: 1, R: A}
C:
0: {write: 1, R: D}
D:

[simocasaz]

[MariaFrancesca6]

Table of instructions:

blank: '0'
 start state: A
 table:
   A:
     0: {write: 1, L: B}  
     1: {write: 0, R: C}
   B:
     0: {write: 1, R: A}
   C:
     0: {write: 1, R: D}
   D:

Starting state:

Final state:

[Sergpoipoip]

[Alice-Ant]

The machine starts in state A. If it reads a 0 or 1 in state A, it writes 1, moves right, and transitions to state B. In state B, if it reads a 0, it writes 0, moves left, and transitions to state C. If it reads a 1, it writes 1, moves right, and stays in state B. In state C, regardless of the input symbol, it writes 0, moves right, and transitions to the final state D. Once in state D, the machine halts and does not have any instructions specified for this state.

[enricabruno]

Initial state:

Final state: