Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 0: Q19P (page 1)

In Corollary 4.18, we showed that the set of all languages is uncountable. Use this result to prove that languages exist that are not recognizable by an oracle Turing machine with an oracle for ATM.

Short Answer

Expert verified

The given statement is proved.

Step by step solution

01

Turing Recognizable

A language L is said to be Turing Recognizable if and only if there exist any Turing Machine (TM) which recognize it i.e., Turing Machine halt and accept strings belong to language L and will reject or not halt on the input strings that doesn’t belong to language L.

02

Proof of the statement.

From Corollary 4.18 we can understand that a Turing machine with oracle will be countable but we cannot prove reducibility, decidability and recognisability without oracle.

But we know that set of all the language L is uncountable. Let say a language L can be map to binary vector to its character vector. Now this binary vector is infinite and made up of two strings of zero’s and one’s.

This means that the group of language cannot be placed to their corresponding group of Turing Machines even oracle is present.

As the group of all language cannot be placed in set of all Turing Machine, so some language are not recognizable by oracle Turing Machine to get access ATM.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Let
fx=3x+1foroddxx/2forevenx

for any natural number x . If you start with an integer x and iterate f , you obtain a sequence, x,fx,ffx,......Stop if you ever hit 1. For example, if x=17 , you get the sequence 17,52,26,13,40,20,10,5,16,8,4,2,1 .Extensive computer tests have shown that every starting point between 1 and a large positive integer gives a sequence that ends in 1 . But the question of whether all positive starting points end up at 1 is unsolved; it is called the 3x+1 problem. Suppose that ATMwere decidable by a TM H. Use H to describe a TM that is guaranteed to state the answer to the 3x+1 problem.

Use the procedure described in Lemma 1.55 to convert the following regular expressions to nondeterministic finite automata.


a.(0∪1)*000(0∪1)*b.((00*11)∪01)*c.∅*

In both parts, provide an analysis of the time complexity of your algorithm.

a. Show thatEQDFA∈P.

b. Say that a languageAisstar-closedifA=A*. Give a polynomial time algorithm

to test whether a DFArecognizes a star-closed language. (Note that EQNFAis not

known to be in P.)

a. Give an NFA recognizing the language (01∪001∪010)*.

b. Convert this to an equivalent DFA. Give only the portion of theDFAthat is reachable from the start state.

Give a counter example to show that the following construction fails to prove that the class of context-free languages is closed under star. Let A be a CFL that is generated by the CFG G=(V,∈,R,S). Add the new ruleS→SS and call the resulting grammar. This grammar is supposed to generate A*.
See all solutions

Recommended explanations on Computer Science Textbooks

Data Structures

Read Explanation

Computer Network

Read Explanation

Data Representation in Computer Science

Read Explanation

Computer Systems

Read Explanation

Algorithms in Computer Science

Read Explanation

Issues in Computer Science

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free