Register

Problem

271 views

1 Answer

3 votes
3 votes
Equality Test for TM Theorem:

EQTM is undecidable Let EQTM be the language { <M1 , M2>| M1 , M2 are TMs, L(M1 ) = L(M1 ) }
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
1 answer
2
saurabh rai asked Oct 26, 2016
2,044 views
class of language
1. L = {<M>|M is a TM and L(M) is countable} 2. L = {<M>|M is a TM and L(M) is uncountable} what is the class of 1 and 2 recursive/RE/NOT RE
1. L = {<M>|M is a TM and L(M) is countable}2. L = {<M>|M is a TM and L(M) is uncountable}what is the class of 1 and 2 recursive/RE/NOT RE
User Avatar
17 votes
17 votes
4 answers
3
gatecse asked Aug 20, 2014
5,812 views
L(M) is infinite
$L= \{\langle M\rangle \mid L(M)\text{ is infinite}\}$ $L$ is RE but $L'$ is not RE Both $L$ and $L'$ are RE $L$ is not RE but $L'$ is RE Both $L$ and $L'$ are not RE
$L= \{\langle M\rangle \mid L(M)\text{ is infinite}\}$$L$ is RE but $L'$ is not REBoth $L$ and $L'$ are RE$L$ is not RE but $L'$ is REBoth $L$ and $L'$ are not RE
User Avatar
1 votes
1 votes
1 answer
4
vedantk asked Jan 10
155 views
Is it DCFL or CFL?
If it’s DCFL then also construct the DPDA ?
If it’s DCFL then also construct the DPDA ?
User Avatar
Link Copied!