Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 0: Q25P (page 1)

Give an example of an undecidable language B, where B≤mB.

Short Answer

Expert verified

is an example of undecidable language.B=1,T:T∈H∪0,T:T∉H

Step by step solution

01

Undecidability

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time.

02

Example of undecidable language

Assume H : Language of all the Turing Machine which halts on empty input. This shows H is undecidable.

Now, let us define B as:


Here, T is also a Turing Machine for some language.

If B is decidable, then a Turing Machine M for language B will show the existence of a TM M' which will decide H . Also M' with input T must run M on input (1,T) .

Also, for a TM T and y∈0,1we will have:

y,T∈B⇔1-y,T∉B⇔1-y,T∉B

So, B reduces to Band B is not decidable as H is not decidable because no Turing Machine exists M' to decide it as stated in starting of the solution.

Hence, B is undecidable but yet.

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.

Show that EQTM'mEQTM'

Question: Let B be the set of all infinite sequences over {0 , 1}. Show that B is uncountable using a proof by diagonalization.

Show that for any two languages AandB , a language J exists, where A≤TJandB≤TJ.

A two-dimensional finite automaton (2DIM-DFA) is defined as follows. The input is an m×nrectangle, for any m,n≥2. The squares along the boundary of the rectangle contain the symbol # and the internal squares contain symbols over the input alphabet ∑. The transition function δ:Q×∑∪#→Q×L,R,U,Dindicates the next state and the new head position (Left, Right, Up, Down). The machine accepts when it enters one of the designated accept states. It rejects if it tries to move off the input rectangle or if it never halts. Two such machines are equivalent if they accept the same rectangles. Consider the problem of determining whether two of these machines are equivalent. Formulate this problem as a language and show that it is undecidable.
See all solutions

Recommended explanations on Computer Science Textbooks

Issues in Computer Science

Read Explanation

Databases

Read Explanation

Computer Programming

Read Explanation

Theory of Computation

Read Explanation

Algorithms in Computer Science

Read Explanation

Problem Solving Techniques

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