Skip links

Skip to primary navigation
Skip to content
Skip to primary sidebar

Main navigation

GATE Overflow Home
- GATE Overflow
GATE Subjects
Blog
GATE CSE Resources
About Us

Resource Portal of GATE Overflow

turing machine

Rices Theorem with Examples

September 23, 2015 by Arjun Suresh 21 Comments

How to apply Rice’s theorem to solve decidability problems

Share this:

Twitter
WhatsApp
Facebook

Like this:

Like Loading...

Filed Under: Theory of Computation Tagged With: rices theorem, turing machine, undecidability

Primary Sidebar

GATE CSE 2025 Syllabus
GATE CSE 2022 Admissions, Results and Placement Responses
GATE CSE 2021 Admission Responses
GATE CSE Books – More Options
ISI PCB Previous Year Papers with Solution

QnA

CSE
Aptitude

Answered: GATE CSE 2017 Set 1 | Question: 27

a non reentrant lock means that suppose a thread holds a lock and tries to hold the same lock again, it wont be possible as it would be blocked and [...]

Answered: GATE CSE 2021 Set 2 | Question: 2

use range search it has O(height+range) .In min heap max element is present in leaf node "height=logn" and there are "n total leaf node" . now apply O(logn+n)=O(n) [...]

Answered: GATE CSE 2017 Set 1 | Question: 13

memory leak occurs as because while executing the code we are not removing the previous allocated memory through pointer x , although the new allocated memory is deleted. [...]

Answered: GATE CSE 2017 Set 1 | Question: 02

Answered: GATE CSE 2017 Set 1 | Question: 02

AAccording to above graph Now let's understand the que. It given "For all of x there exist some y for which R(x,y) is true"Now option 1 given for some y there [...]

Answered: GATE IT 2005 | Question: 62

Answered: GATE IT 2005 | Question: 62

Here, we have considered that $R1$ and $R2$ are single instance resources.Hence, option $C$ is correct. Hope this helps :) [...]

Answered: The actual ___________ of Wilson's position was always ___________ by his refusal to compromise after having initially agreed to negotiate a settlement. Outcome, foreshadowed Logic, enhanced Rigidity, betrayed Uncertainty, alleviated Cowardice, highlighted.

Outcome, foreshadowed. [...]

Answered: CAT 1997 | Question: 145

Arrange the sentences in a proper sequence so as to make a coherent paragraph. A. In emission trading, the government fixes the total amount of pollution that is acceptable to maintain a desired level of air quality. B. Economists argue that this approach makes air pollution control more costeffective than the current practice of fixing air-pollution standards and expecting all companies to pollute below these standards. C. The USA uses emissions trading to control air pollution. D. It then distributes emission permits to all companies in the region, which add up to the overall acceptable level of emission. BADC ACDB CBAD DBAC

Answered: If x = 5y, and 15y = 3a, what is the value of x?

15y = 3a or, y = a/5 x = 5y or, x = a So, the answer is a. [...]

Answered: CAT 2023 Set-3 | Quantitative Aptitude | Question: 20

Option A is the answer Reason: Given, an = 46 + 8n = 6 + 8(5 + n) bn = 98 + 4n = 2 + 4(24 + n) Now understand how an and [...]

Copyright © 2024 · by BizzThemes · WordPress · Log in

Loading Comments...

You must be logged in to post a comment.

%d