Decidability+TM

Question

Decidability+TM

Rahul Jain25 asked Dec 13, 2016

232 views

See all

Please log in or register to answer this question.

Related questions

1 votes

3 answers

1

gmrishikumar asked Dec 10, 2018

1,735 views

Halting problem of TM which recognize recursive languages is undecidable?
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)

Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)

gmrishikumar

1.7k views

gmrishikumar asked Dec 10, 2018

1 votes

1 answer

2

Mk Utkarsh asked Sep 15, 2018

1,505 views

TM that accepts input string x
$D = \left \{ M \mid \ M \text{ is a TM that accepts the input string } x \right \}$ What is complement of D and is it Decidable, Turing recognizable or not Turing recognizable?

$D = \left \{ M \mid \ M \text{ is a TM that accepts the input string } x \right \}$What is complement of D and is it Decidable, Turing recognizable or not Turing recogni...

Mk Utkarsh

1.5k views

Mk Utkarsh asked Sep 15, 2018

11 votes

2 answers

3

sourav. asked Sep 9, 2017

4,531 views

$\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$

My Question $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$I have to check that it is Turing Recogniza...

sourav.

4.5k views

sourav. asked Sep 9, 2017

1 votes

0 answers

4

amitarp818 asked Dec 28, 2023

238 views

Decidability
L(M)={0} We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable) I don’t understand why this is not decidable. We can easily create a turing that accepts this language

L(M)={0}We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable)I don’t ...

amitarp818

238 views

amitarp818 asked Dec 28, 2023

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

Decidability+TM

Please log in or register to add a comment.

Please log in or register to answer this question.

0 Answers

Related questions

0 reply

Please log in or register to add a comment.

Please log in or register to answer this question.

0 Answers

Related questions

0