geeksforgeeks
closed

Sunil8860 asked Aug 14, 2017 • closed Aug 14, 2017 by Arjun

198 views

See all

Related questions

1 votes

0 answers

Sunil8860 asked Aug 14, 2017

361 views

geeksforgeeks
L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w1, w2, w3, … Define another language L2 over Σ Union {#} as {wi # wj : wi, wj ∈ L1, i < j}. Here # is a new symbol. Consider the following assertions. S1 : L1 is recursive implies L2 is recursive S1 is correct can anyone explain how?

L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w1, w2, w3, … Define another language L2 over Σ Union {#} as {wi # ...

Sunil8860

361 views

Sunil8860 asked Aug 14, 2017

0 votes

0 answers

dopq12 asked Mar 5

98 views

Hopcroft, Ullman Theorem 9.7 Reductions
There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and accept when given itself as input. It is known and proved that Ld is a non- ... and Ld is non-RE, ATM must be non-RE. But we know that ATM is Recursively Enumerable and undecidable. How is this possible?

There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and accept when given itself a...

dopq12

98 views

dopq12 asked Mar 5

5 votes

1 answer

GO Classes asked Jan 28

502 views

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 55
Recall that a Turing machine $\text{T}$ can be represented or 'coded' by an integer $m$. Let us write 'the $m$ th Turing machine' to mean the Turing machine coded by $m$. Which of the following sets is not ... machine halts on the input $m$. The set of $n$ such that all Turing machines halt on the input $n$.

Recall that a Turing machine $\text{T}$ can be represented or 'coded' by an integer $m$. Let us write 'the $m$ th Turing machine' to mean the Turing machine coded by $m$....

GO Classes

502 views

GO Classes asked Jan 28

0 votes

0 answers

Ramayya asked Jan 7

149 views

ISRO 2024
which of the following statements is NOT true? If a language is recursive it complement is recursive If a language is recursive its complement is recursively enumerable If a language and its complement are recursively enumerable it is recursive If a language is recursively enumerable its complement is also recursively enumerable

which of the following statements is NOT true?If a language is recursive it complement is recursiveIf a language is recursive its complement is recursively enumerableIf a...

Ramayya

149 views

Ramayya asked Jan 7

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

geeksforgeeks
closed

Please log in or register to add a comment.

0 Answers

Related questions

0 reply

Please log in or register to add a comment.

0 Answers

Related questions

0