Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Huji 67521 Computability > Computability - Turing Machines > Flashcards

Computability - Turing Machines Flashcards

1
Q

Define a Turing Machine

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Define: Configuration of a Turing Machine

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Define: the language of a Turing machine

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Define the class R

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Define the class RE

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Define the class co-RE

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Define the class R using other classes

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the language Atm?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Does the language Atm belong to:

R

RE

co-RE

Does ATMc belong to RE?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Define HALTTM

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is a Universal TM?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Is HALTTM in R? is it in RE?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Define a mapping reduction from A to B

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is the Reduction Theorem?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Define the language REGTM.

To where does it belong?

A

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

REGTM ∈ (RE ∪ coRE)c

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Define: An accepting run of a TM

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Define the language NONTRIVIALTM.

To what class does it belong?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Define the language INFTM.

To what class does it belong?

A

INFTM ∈ (RE ∪ coRE)c

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is Rice’s Theorem?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q
A
The Rice's Theorem Lemma
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Define a nondeterministic TM.

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

When is such a machine considered a decider?

A
28
Q

What is The Rice’s Theorem Lemma?

A
29
Q
A
30
Q

Compare the languages of non deterministic TMs and deterministic TMs.

A
31
Q

Define REACHTM, to what class does it belong?

A
32
Q

Define EQTM, to what class does it belong?

A
33
Q

if L is in R, is Lc in R?

Is R closed for concatenation?

Is R closed to union?

A

Yes, Yes and Yes

34
Q

Let L be a language in RE/coRE.

What language is definitely not in RE?

A

Lc

35
Q

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

A
  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 Lc < (Language in RE).
36
Q

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

A

You could show that:

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

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

A

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

38
Q

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

A
39
Q

Does the language ∑* belong to RE

A

Yes

40
Q
A
41
Q
A
42
Q

Is RE closed to intersection?

A

RE is closed to intersection.

43
Q

Define the language HALT All

A
44
Q

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

A

Rice’s Theorem.

45
Q

What is the structure of the proof?

A
46
Q
A
47
Q

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

A

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

For example: ALLTM < L.

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

48
Q
A
49
Q

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

A

Describe a TM that recognizes the language.

50
Q

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

A

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

51
Q

Important Question:

A

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).

52
Q
A
53
Q
A
54
Q

The languages of what TMs are contained in RE?

A

The language of every TM is in RE.

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

55
Q
A

So L is the set of all TMs.

56
Q

important Question

2017 moed A

A

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

57
Q

2017 moead A

A

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.

58
Q

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

2018 Moed A

A
59
Q

2018 Moed A

A
59
Q

2018 Moed A

A
60
Q

2018 Moed B

A
  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.
61
Q

Prove the claim is false.

2018 Moed B

A
  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.
62
Q

How many configurations in a TM?

A
63
Q

2018 Moed B

A
64
Q

2018 Semester B Moed B

A

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”.

Huji 67521 Computability (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions