ox cs education

Gurdeep Saini asked Nov 14, 2018

286 views

0 votes

alternate definition of semi decidable

Definition: an enumerator for a language L ⊂ Σ ∗ is a TM that writes on its output tape #x1#x2#x3# . . . and L = {x1, x2, x3, . . .}.

pleasee elaborate this

http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/slides3.pdf

Theory of Computation
theory-of-computation
decidability

+ –

Gurdeep Saini asked Nov 14, 2018

Gurdeep Saini

286 views

See all

0 Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

0 votes

semi decidable or partially decidable or turing recognizable lang says a TM will tell YES if it accepts that language. But it can not say anything if it loops forever or rejects that language.

pps121 answered Nov 14, 2018

pps121

See all

1 1 comment

Gurdeep Saini

commented Nov 14, 2018

everyone know this defination explain which i wrote

0 votes

Please log in or register to add a comment.

Voting & Accepting an answer helps improve the community

← Previous Next →

← Previous in category Next in category →

Related questions

2 votes

0 answers

akb1115 asked Jul 18, 2017

788 views

Rice theorem Example from (https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf)
L={<M>: M is a TM that accepts all even numbers } Why it is not recursively enumerable language???

L={<M>: M is a TM that accepts all even numbers } Why it is not recursively enumerable language???

akb1115

788 views

akb1115 asked Jul 18, 2017

Theory of Computation
rice-theorem
theory-of-computation
decidability

+ –

0 votes

0 answers

Arpit Dhuriya asked May 24, 2017

417 views

http://www.cs.rice.edu/~nakhleh/COMP481/
Can anybody please explain this reduction and rice theorem. http://www.cs.rice.edu/~nakhleh/COMP481/ Thanks

Can anybody please explain this reduction and rice theorem.http://www.cs.rice.edu/~nakhleh/COMP481/Thanks

Arpit Dhuriya

417 views

Arpit Dhuriya asked May 24, 2017

Theory of Computation
theory-of-computation
rice-theorem
decidability

+ –

0 votes

0 answers

dopq12 asked Mar 5

126 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

126 views

dopq12 asked Mar 5

Theory of Computation
decidability
theory-of-computation
turing-machine
reduction
recursive-and-recursively-enumerable-languages

+ –

4 votes

0 answers

GO Classes asked Feb 5

632 views

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 65
Which of the following statements are true for every language $\mathrm{L} \subseteq\{0,1\}^*?$ $L^{\star}$ is infinite. $L$ is accepted by some DFA if and only if $L$ is accepted by some NFA. If $\mathrm{L}$ is the ... $\mathrm{L}$ is undecidable. If $\mathrm{L}$ is the union of two decidable languages, then $\mathrm{L}$ is decidable.

Which of the following statements are true for every language $\mathrm{L} \subseteq\{0,1\}^*?$$L^{\star}$ is infinite.$L$ is accepted by some DFA if and only if $L$ is ac...

GO Classes

632 views

GO Classes asked Feb 5

Theory of Computation
goclasses2024-mockgate-14
theory-of-computation
decidability
multiple-selects
2-marks

+ –

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

0 reply

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

1 1 comment reply

Please log in or register to add a comment.

Related questions

0

1 1 comment