Register

self doubt

210 views

1 Answer

2 votes
2 votes

TM accepting ∊  simply means out TM will always halts on input ∊.

This is exactly Halting problem which states that 'We can't make an algorithm that can decide whether a particular TM will accept input string 'W' or not'.

in out case here string is ∊ , and it's RE but not REC means semi decidable.

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
prasoon054 asked Dec 7, 2023
184 views
Countable Sets Self Doubt
Is countable sets part of GATE CS 2024 syllabus?
Is countable sets part of GATE CS 2024 syllabus?
User Avatar
3 votes
3 votes
2 answers
2
Jiten008 asked Oct 24, 2023
362 views
TOC - Self Doubt
Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$ And if $CFL$ can you write the equivalent $CFG$ for this ?
Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$ And if $CFL$ can you write the equivalent $CFG$ for this ?
User Avatar
1 votes
1 votes
1 answer
3
Swarnava Bose asked Aug 26, 2023
274 views
Self Doubt from GoClasses Test Series
If L= { a^p | where p is any prime number }, then what is:- i) L+ ii) L* iii)L^3
If L= { a^p | where p is any prime number }, then what is:- i) L+ ii) L*iii)L^3
User Avatar
Link Copied!