Ch 3: Church-Turing Thesis

Question 1

How do we show that a type of Turing machine recognizes the class of Turing-recognizable languages?

Answer 1

A language is Turing-recognizable if some Turing machine recognizes it

(iow, all the strings of that language are accepted by the TM)

If one TM can recognize the language, then its in the class of TM recognizable languages.

So, to show that a type of Turing machine recognizes the class of Turing-recognizable languages, we need to show that it is equivalent to another TM.

BL TWO MACHINES ARE EQUIVALENT IF THEY RECOGNIZE THE SAME LANGUAGE**

Question 2

What is a Turing recognizable language?

Answer 2

Any language that a Turing machine can recognize.

The collection of strings that M accepts is the language of M or the language recognized by M

Remember, recognize means that

Question 3

What is meant by a Turing machine accepting an input w?

Answer 3

A sequence of configurations exists such that

1. C1 is start of M on w
2. each Ci yields Ci+1
3. Ck is an accepting config

Question 4

What are the three options for a TM that starts?

Answer 4

It can accept, reject, or loop

Question 5

What does it mean if a TM accepts an input?

Answer 5

It does not fail or loop

Question 6

What is the difference between a decider and a non-decider?

Answer 6

A decider always halts. It either accepts or rejects, but it does not loop

Question 7

What does it mean to decide a language? How is this different than recognizing a language?

Answer 7

A decider always makes a decision to accept or reject, it never loops. A machine that recognizes a language could loop forever, and we wouldn’t know if we were waiting for the answer or if it was stuck in a loop.

Question 8

What is another name for Turing-recongnizable and for Turing-decidable? Why do these names make sense?

Answer 8

Recursively enumerable language == Turing-recognizable

Recursive language == Turing-decidable

[INSERT REASON WHY]

Question 9

Why do we use Turing machines after all?

Answer 9

They capture ALL algorithms, algorithmic processes.

Question 10

Why do we encode objects?

Answer 10

Because the input to a Turing machine is always a string, and any object can be encoded into a string.

Question 11

Does the type of encoding of an object matter to a Turing Machine?

Answer 11

Not really. because it can switch back and forth to different encodings if needed.

Question 12

Why can’t we use E.CFG to prove that EQ.CFG is decidable, like we did for EQ.DFA and E.DFA?

Answer 12

Because CFL’s are NOT closed under complement or intersection.

Question 13

What are disjoint languages?

Answer 13

Languages A and B, where all the strings that are acceptable to A are NOT acceptable to B

Question 14

What is the definition of Turing co-recognizable?

Answer 14

????

Question 15

What is an enumerator?

Answer 15

It is a Turning machine attached to a printer.

Question 16

When is a language Turing-recognizable?

Answer 16

The definition is, if ‘some’ TM recognizes a language, it’s Turing-recognizable.

IFF some NTM recognizes it.

IFF some multi-tape TM recognizes it.

Question 17

How do we show that two TM’s are equivalent?

Answer 17

We can simulate one with the other.

Question 18

What are the 4 differences between a TM and an FA?

Answer 18

1. TM tape is infinite
2. TM can read AND write to tape
3. TM can move left and right along tape
4. Accept and reject states of TM take effect immediately.

Question 19

Explain the statement, recognizers ARE more powerful than deciders.

Answer 19

Since, A.TM is undecidable, ….

basicially, requiring a TM to halt on all inputs restricts the kinds of languages that it can recognize.

Question 20

What is the definition of a universal turing machine?

Answer 20

a Turing Machine that can simulate any other Turing machine.

Question 21

How do we know that two sets A and B are the same size?

Answer 21

If there is a one-one and onto function that maps A to B. This is also called a correspondence.

In other words, every element from A has a unique element of B, and each element of B has a unique element of A.

In other words, all the elements are paired off without duplication

Question 22

How does the theorem that R is uncountable relate to the theory of computation?

Answer 22

It shows that some languages are not decidable or even Turing recognizable, for the reason that there are uncountably many languages, yet only countably many Turing machines.

Because each Turning machine can recognize a single language, and there are more languages than Turning machines, some languages are not recognized by any Turing machine.

Such languages are not Turing-recognizable.

Question 23

What does it mean if a language and its complement are both Turing-recognizable?

Answer 23

That language is decidable.

Question 24

What is true of undecidable languages with regard to their complements?

Answer 24

Undecidable languages have either themselves, or their complement NOT-Turing-recognizable.

Question 25

What is the definition of co-Turing-recognizable?

Answer 25

It is the complement of a Turing-recognizable language.

Question 26

Why is the complement of A.TM NOT Turing-recognizable?

Answer 26

We know that A.TM is Turing recognizable. If complement of A.TM were recognizable, then A.TM would be decidable. But we’ve shown that A.TM is not decidable, so we conclude that the complement of A.TM must not be Turing-recognizable.