Brainscape's Knowledge GenomeTM

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


See full index

CS3052: Computational Complexity > 4: The limits of computation > Flashcards

4: The limits of computation Flashcards

1
Q

What is the Church-Turing thesis?

A

That any algorithmic procedure can be implemented and carried out on a Turing machine.

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

What does it mean for a programming language to be Turing-complete?

A

A programming language is Turing-complete if it is able to simulate every Turing machine (or equivalently, the Universal Turing Machine). Automatons and other machines can be said to be Turing-complete as well as programming languages so long as they too can simulate all Turing machines.

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

How does being Turing-complete affect the power of programming languages?

A

Languages are more powerful when Turing-complete rather than Turing-incomplete in that they are able to run some number of TMs that they would not be able to run otherwise. Note, however, that despite the Turing machine-based architecture of modern computers, regular languages (that can run on TMs) are a tiny number of languages so there is a large capacity of power for languages outside of Turing-completeness.

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

Prove that the language { | M is a TM that halts on input w} is not decidable. What does this signify?

A

??

This is the halting language of the halting problem proves that the halting problem is therefore unsolvable.

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

Prove that the set of all infinitely-long words from the alphabet {0, 1} is uncountable.

A

??

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

What is decidability?

A

A true/false decision problem is decidable if there exists an effective method, here a TM, for deriving the correct answer.

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

What is a decision problem?

A

A decision problem is any well-specified problem whose result is true or false.

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

True/false: finding whether there exist algorithms to solve decision problems is equivalent to finding whether one can solve these problems using a Turing machine. Why?

A

True, since by the Church-Turing thesis says there is a TM that exists to implement any algorithm (that will accept when it results in a true solution).

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

What is a decider?

A

A TM that always halts (accepts or rejects) and never infinitely loops.

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

True/false: all regular languages are context-free?

A

True.

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

What does it mean for a language to be Turing-recognisable?

A

A language is Turing-recognisable if and only if there exists a Turing Machine which will halt and accept only the strings in that language and for strings not in the language, the TM either rejects or does not halt at all.

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

True/False: Not all Turing-decidable languages are Turing-recognisable?

A

False, all Turing-decidable languages are Turing-recognisable.

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

Prove that all Turing-decidable languages are Turing-recognisable.

A

Consider a Turing-decidable language L. By assumption of the Church-Turing thesis, there is a Turing machine M such that L = L(M) and M is a decider. So, in particular, M is a Turing machine that recognises L.

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

True/false: the union of a finite number of countable sets is countable?

A

True. Since the product will also be a countable number of numbers from all the sets.

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

True/false: there are countably many languages that are not Turing recognisable?

A

False. There are uncountably many languages that are not Turing recognisable.

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

Is the language { | M is a TM which accepts the word w} Turing-recognisable?

A

Yes, the acceptance language is Turing-recognisable but it is not decidable.

17
Q

What is the acceptance problem?

A

To find a decider TM for the acceptance language, AT = { | M is a TM which accepts the word w}.

18
Q

What is the proof of Rice’s theorem?

A

??

19
Q

Prove that the language { | M is a TM which accepts the word w} is not solvable. What does this signify?

A

??

Since this is the acceptance language, from the acceptance problem, the acceptance problem is therefore not solvable.

20
Q

What is the Halting Problem?

A

To find a decider TM for the halting language, AT = { | M is a TM which halts on the word w}.

21
Q

Is the language { | M is a TM that halts on input w} decidable? What does this signify?

A

No, the halting language of the halting problem is not decidable. This proves that the halting problem is therefore unsolvable.

22
Q

What is a property of a Turing machine?

A

A property P of a TM is a statement that is true or false about the TM.

23
Q

What is a non-trivial property of a Turing machine?

A

A property P of a TM (a statement that is true or false about the TM) is non-trivial when there is at least one TM for which P is true and at least one for which P is not (i.e. P not always true and P not always false).

24
Q

What is Rice’s theorem?

A

Let P be a nontrivial property of the languages recognised by TMs. Then the following language is undecidable:
LP = { | M satisfies P}.
That is, there is no algorithm to decide whether a TM satisfies P.

25
Q

Prove that all decidable languages are recognisable.

A

??

26
Q

True/false: If a language and its complement are Turing-recognisable, then the language is decidable.

A

True.

27
Q

Prove that if a language and its complement are Turing-recognisable, then the language is decidable.

A

??

28
Q

Prove that the language { | M is a TM which accepts the word w} is not Turing-recognisable>

A

??

29
Q

What does it mean for a set to be countable?

A

A set is countable if it is finite or its elements can be put into an infinite list.

30
Q

True/false: the union of countably many countable sets is countable?

A

True. Since the product will also be a countable number of numbers from all the sets.

31
Q

True/false: the set of all infinitely-long words from the alphabet {0, 1} is countable.

A

False. The set of all infinitely-long words from the alphabet {0, 1} is uncountable.

32
Q

True/false: most languages aren’t Turing-recognisable?

A

True: the vast majority of languages are not Turing-recognisable?

33
Q

True/false: there are only countably many languages that are Turing-recognisable?

A

True.

34
Q

Prove that there are only countably many languages that are Turing
recognisable.

A

??

35
Q

Prove that there are uncountably many languages that are not Turing recognisable.

A

??

36
Q

True/false: all context-free languages are decidable?

A

True.

37
Q

True/false: all decidable languages are recognisable?

A

True.

38
Q

Prove that all regular languages are context-free.

A

??

39
Q

Prove that all context-free languages are decidable.

A

??

CS3052: Computational Complexity (9 decks)

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