Lecture "Computability", exercise 3

comp-think / 2024-2025

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. 2024/2025).

12 stars 0 forks source link

Lecture "Computability", exercise 3 #11

Open essepuntato opened 2 weeks ago

essepuntato commented 2 weeks ago

Consider an algorithm that takes as input a 0-1 sequence of exactly five symbols and returns 1 if the sequence contains at least three 1s in any order, while it returns 0 otherwise. Implement the algorithm with a Turing machine, where the cell corresponding to the starting position of the head is where the final result must be stored. Also, the five cells following the starting position of the head are initialised with the 0-1 sequence of five symbols used as input of the algorithm.

ValkyrieCain9 commented 1 week ago

I haven't checked all the possible combinations for this but I am pretty sure it should work

input: '11011' blank: ' ' start state: step table: step: 0 : R 1 : {R: yes1} ' ': {L: result0}

yes1: 0 : R 1 : {R: yes2} ' ': {L: result0}

yes2: 0 : R 1 : {L: result1} ' ': {L: result0}

result0: [0,1] : L ' ' : {write: 0, L: done}

result1: [0,1] : L ' ' : {write: 1, L: done} done:

KikaYang commented 1 week ago

Thanks for Regina's example. Now I know what is the meaning of ' ': {L: done}.

theair-hub commented 4 days ago

input: 'x11111' #or whatever sequence of 0 and 1 with "x" as starting position blank: ' ' start state: start

table: start: 'x': {R: q1} q0:

'x': {write: 0, L:}

q1: '1': {R: q2} '0': {R: q1} ' ': {L: q0} q2: '1': {R: q3} '0': {R: q2} ' ': {L: q0} q3: '1': {L: q4} '0': {R: q3} ' ': {L: q0} q4:

'x': {write: 1, L:}

done:

yutong316 commented 3 days ago

Current State | Current Symbol | Write Symbol | Move Direction | Next State -- | -- | -- | -- | -- A | 0 | 0 | Right | A A | 1 | 1 | Right | B B | 0 | 0 | Right | B B | 1 | 1 | Right | C C | 0 | 0 | Right | C C | 1 | 1 | Right | D D | 0 | 0 | End | End D | 1 | 1 | End | End D | 0 | 0 | End | End

ERendall commented 15 hours ago

I do not know how to film the visualisation, but I hope this suffices. Again, I have tried to be thorough, keeping the calculations simple (although it may not appear like that...).

The instructions on the side may give some idea as to how things work! But, in short, I used the same logic as found in exercise 2, accounting for a greater number of combinations.

Again, happy to help anyone if I am being unclear!