REC

Question 1

• Given property P over RE, tell if Lp is REC/RE/NON-RE.
  
  • Exams: 19-01-22, 20-01-27, 20-02-17, 21-01-25, 21-02-12, 21-06-28,
  • PDF: 3.4, 3.5, 3.6, 3.7, 3.8,

Answer 1

…

Question 2

• Given L1 and L2, tell if intersection/concatenation/… are RE/REC/…
  
  • Exams: 19-01-22, 21-01-25,
  • PDF: 3.10,

Answer 2

…

Question 3

• Given L={M(enc),…}, tell if L is RE (reduction)
  
  • Exams: 19-02-13, 19-01-22, 19-09-13, 21-02-12, 21-06-28,
  • PDF: 3.9, 3.10.3, 3.11, 3.12,

Answer 3

…

Question 4

• Given L, specify Turing machine M that accepts it and stops for each input.
  
  • Exams: 19-06-28,
  • PDF: 3.1, 3.2, 3.3,

Answer 4

…

Question 5

• Theory:
  
  • Define the notion of property of the languages generated by TMs and state Rice’s theorem. Provide the proof of Rice’s theorem that we have developed in class. (21-09-03,

Answer 5

…

Question 6

• Theory:
  
  • definizione di macchina di Turing nondeterministica e la definizione di linguaggio da questa accettato. Dimostri che ogni linguaggio accettato da una macchina di Turing nondeterministica può essere accettato da una macchina di Turing deterministica.

Answer 6

…

Question 7

• Theory:
  
  • Richiamare la definizione del linguaggio Lne. Dimostrare che Lne non appartiene alla classe REC. Attenzione: è richiesta la dimostrazione svolta in classe per questo teorema, non utilizzare il teorema di Rice. (20-02-17,

Answer 7

…