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.

[vattelalberto]

I don't know if I got the excercise right, I managed to write an algorithm that only works with a blank input. I could not find one that works for every input that only uses 4 nodes as described in the excercise (I only found one that works with inputs composed of 3 or more numbers)

https://gist.github.com/vattelalberto/1b3b144a7e3bc0de00e9e754ec2e5f89 (can be imported in turingmachine.io)

[corrado877]

I'm not sure if I got it right but I've tried anyway.

https://gist.github.com/corrado877/ab4702e8dbd0f39c36ca2523327e4298

[ChiaraParravicini]

https://gist.github.com/ChiaraParravicini/9cd8b32a514679a2aa1ab80dae28936f

[ranacoskun]

Table of instructions:

[delete4ever]

Sorry to present my answer in an old-school way because I'm still used to visualizing my thoughts with a pen& paper(＞人＜；). And I think these instructions only 100% work when all the cells are initialized as 0.

[falaimo99]

This code works on turingmachine.io

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

[alka2696]

The table of instructions of a Turing machine with four states:

Works on (http://turingmachine.io/)

[mjavadf]

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

[SalvatoreDiMarzo]

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

[lucia1299]

Current state | Read | Write | Move head | Next state -- | -- | -- | -- | -- A | 0 or 1 | 0 | R | B B | 0 or 1 | 1 | L | A A | 0 or 1 | 0 | L | C C | 0 or 1 | 1 | R | A

[matteo-guenci]

Current state	Tape symbol	Write symbol	Move head	Next state
A	0	1	Right	B
A	1	0	Left	C
B	0	1	Right	A
C	0	1	Right	D

[n1kg0r]

Table format

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

turingmachine.io code format

input: '0'
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: