Computability - Turing Machines

Question 1

Define a Turing Machine

Answer 1

Question 2

Define: Configuration of a Turing Machine

Answer 2

Question 3

Define: the language of a Turing machine

Answer 3

Question 4

Define the class R

Answer 4

Question 5

Define the class RE

Answer 5

Question 6

Define the class co-RE

Answer 6

Question 7

Define the class R using other classes

Answer 7

Question 8

Answer 8

Question 9

What is an Enumerator, and what does it have to do with RE?

Answer 9

Question 10

What is the language A_tm?

Answer 10

Question 11

Does the language A_tm belong to:

R

RE

co-RE

Does A_TM^c belong to RE?

Answer 11

Question 12

Define HALT_TM

Answer 12

Question 13

What is a Universal TM?

Answer 13

Question 14

Is HALT_TM in R? is it in RE?

Answer 14

Question 15

Define a mapping reduction from A to B

Answer 15

Question 16

What is the Reduction Theorem?

Answer 16

Question 17

Answer 17

Question 18

Define the language HALT^ė_TM , Does it belong to R?

Answer 18

Question 19

Define the language REG_TM.

To where does it belong?

Answer 19

REG_TM = {M : L(M) is regular}

REG_TM ∈ (RE ∪ coRE)^c

Question 20

Define: An accepting run of a TM

Answer 20

Question 21

Answer 21

Question 22

Answer 22

Question 23

Define the language NONTRIVIAL_TM.

To what class does it belong?

Answer 23

Question 24

Define the language INF_TM.

To what class does it belong?

Answer 24

INF_TM ∈ (RE ∪ coRE)^c

Question 25

What is Rice’s Theorem?

Answer 25

Question 26

Answer 26

The Rice's Theorem Lemma

Question 27

Define a nondeterministic TM.

When does a word belong to the language of such a machine?

When is such a machine considered a decider?

Answer 27

Question 28

What is The Rice’s Theorem Lemma?

Answer 28

Question 29

Answer 29

Question 30

Compare the languages of non deterministic TMs and deterministic TMs.

Answer 30

Question 31

Define REACH_TM, to what class does it belong?

Answer 31

Question 32

Define EQ_TM, to what class does it belong?

Answer 32

Question 33

if L is in R, is L^c in R?

Is R closed for concatenation?

Is R closed to union?

Answer 33

Yes, Yes and Yes

Question 34

Let L be a language in RE/coRE.

What language is definitely not in RE?

Answer 34

L^c

Question 35

What are different ways to show that a language L is in R?

Answer 35

1. Build a Turing Machine that decides L and prove correctness and Computability.
2. (If applicable) Show that L is built from sub-languages in R. Use closure properties of R to show that L is also in R.
3. Use 2 reductions: L < (Language in RE) and L^c < (Language in RE).

Question 36

How would you prove that a language L belongs to RE\R?

Answer 36

You could show that:

1. L ∈ RE.
2. L ∉ R. Alternatively: L ∉ coRE.

Question 37

How would you show that a language L is not in R?

Answer 37

By using Rice’s theorem or by showing a reduction from a language not in R to L.

Question 38

How will we prove that a language belongs to (coRE ∪ RE)^c ?

Answer 38

Question 39

Does the language ∑* belong to RE

Answer 39

Yes

Question 40

Answer 40

Question 41

Answer 41

Question 42

Is RE closed to intersection?

Answer 42

RE is closed to intersection.

Question 43

Define the language HALT All

Answer 43

Question 44

How can you show that some languages are not in coRE?

Answer 44

Rice’s Theorem.

Question 45

What is the structure of the proof?

Answer 45

Question 46

Answer 46

Question 47

How could you prove that a language L is in (RE U coRE)^c?

Answer 47

By showing a reduction from a language in (RE U coRE)^c.

For example: ALL_TM < L.

ALL_TM is not in RE and not in coRE, and therefore neither is L.

Question 48

Answer 48

Question 49

What’s and easy way to prove that a language is in RE?

Answer 49

Describe a TM that recognizes the language.

Question 50

What MUST you do before selecting that a language L belongs to (RE U coRE)-complete?

Answer 50

Check if L-Complete belongs to RE (And therefore L belongs to coRE).

Question 51

Important Question:

Answer 51

Note how the reduction is from to (i.e. form TM to TM) and still takes into account what M’ does on a word w. (This should be obvious).

Question 52

Answer 52

Question 53

Answer 53

Question 54

The languages of what TMs are contained in RE?

Answer 54

The language of every TM is in RE.

L(M) belongs to RE for every TM M, because M recognizes L(M).

Question 55

Answer 55

So L is the set of all TMs.

Question 56

important Question

2017 moed A

Answer 56

Note the connection between a TM and a tree, as well as that the reduction does not nead to be polynomeal.

Question 57

2017 moead A

Answer 57

Note the connection between ND-TMs and a configuration tree.
Note that the TM that recognizes L2 doesn’t run M on w as you may have expected, because that doesn’t promis recognition of the language (because the TM is Non deterministic), but instead examins the configuration tree.

Question 58

Important example of such a reduction where new TMs need to be created.

2018 Moed A

Answer 58

Question 59

2018 Moed A

Answer 59

Question 59

2018 Moed A

Answer 59

Question 60

2018 Moed B

Answer 60

1. Note that here when proving a language is in RE, it is simpler to descripte the recognizing TM, as opposed to using a reduction.
2. Note you must do the n thing.

Question 61

Prove the claim is false.

2018 Moed B

Answer 61

1. Note that the reduction is not from Atm. Don’t automaticaly jump to reducing from Atm when showing a language is not in coRE. There are other languages.

Question 62

How many configurations in a TM?

Answer 62

Question 63

2018 Moed B

Answer 63

Question 64

2018 Semester B Moed B

Answer 64

Note:
1. You can’t simply have M’ run M on epsilon to see if it accepts at any point. What if it never does?
2. The way to deal with this is by using some kind of counter, (here we used the length of w to which we have access.)
3. The counter lets us replace:
“If M doesn’t stop - do something”
with
“While M doesn’t stop - do something”.