Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 5: Q29P (page 241)

Show that both conditions in Problem 5.28 are necessary for proving that P is undecidable.

Short Answer

Expert verified

Language P is undecidable.

Step by step solution

01

Undecidability

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

02

Conditions on  P

There were two conditions:

  • Condition (1): P is nontrivial—it contains some, but not all, TM descriptions.
  • Condition (2): P is a property of the TM’s language—whenever,LM1=LM2, we haveM1∈P iffM2∈P .

In Condition (1), we have constructed Turing Machine that ensures that M is a valid Turning Machine description and accepts the input.

In Condition (2), we had constructed a Turing Machine that will reject all the strings.

03

Proving P undecidable

Now, ifis the property of the machine, then P would be ‘Decidable’, but rather these properties is due to two conditions given, that makes P as undecidable.

Hence, both conditions are necessary for proving that P is undecidable.

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

Question: Consider the problem of determining whether a PDA accepts some string of the form {ww|w∈{0,1}*}. Use the computation history method to show that this problem is undecidable.

Question: A two-dimensional finite automaton (2DIM-DFA) is defined as follows. The input is anm×n rectangle, 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,D} indicates 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.

Say that a variable A in CFG G is necessary if it appears in every derivation of some string w∈G. Let NECESSARYCFG={G,AAisanecessaryvariableinG}.

  1. Show that NECESSARYCFG is Turing-recognizable.
  2. Show that NECESSARYCFG is undecidable.

Question: Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.

Show that if A is Turing-recognizable and A⩽mA¯, then A is decidable.
See all solutions

Recommended explanations on Computer Science Textbooks

Problem Solving Techniques

Read Explanation

Big Data

Read Explanation

Computer Organisation and Architecture

Read Explanation

Algorithms in Computer Science

Read Explanation

Data Representation in Computer Science

Read Explanation

Computer Network

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