Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.

Sign up to join this community

Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

Explore our Questions

Ask Question

more tags

Active 3 Bountied Hot Week Month

0

votes

1

answer

7

views

Why is $EQ_{cfg}$ not recognizable but is co-turing-recognizable

turing-machines undecidability computation-models

answered 3 hours ago nir shahar 5,819

0

votes

0

answers

22

views

Name for this theorem on non-decreasing probability of sucess of a deterministic algorithm?

turing-machines halting-problem

modified 15 hours ago fgrieu 363

0

votes

0

answers

11

views

Oracle for LBA halting on some input

turing-machines computability halting-problem

asked 19 hours ago lapb 1

0

votes

1

answer

47

views

Using Rice's theorem to prove undecidability of $E_{TM}$

turing-machines rice-theorem

modified yesterday Community♦ 1

-2

votes

1

answer

310

views

Turing machine on input w tries to move its head past the left end of the tape

formal-languages turing-machines undecidability

modified 2 days ago jeffli 1

0

votes

1

answer

37

views

Reduction of Turing-machine language

turing-machines computability undecidability semi-decidability

modified 2 days ago Community♦ 1

3

votes

2

answers

377

views

If regex describes FSAs, what string formats describe Turing machines?

formal-languages turing-machines finite-automata

modified 2 days ago Pseudonym 15.3k

2

votes

1

answer

27

views

How are two registers are enough to simulate a Turing machine?

turing-machines computation-models

answered Jun 17 at 6:50 Yuval Filmus 254k

0

votes

1

answer

22

views

Question about reduction Proof

complexity-theory formal-languages turing-machines reductions mapreduce

answered Jun 16 at 18:11 nir shahar 5,819

0

votes

1

answer

16

views

Show that the Turing Reduction is transitive: if $A\leq_{T}B$ and $B\leq_{T}C$ then $A\leq_{T}C$

turing-machines

answered Jun 16 at 14:38 Steven 15.5k

1

vote

2

answers

43

views

Prove that { $\langle M \rangle$ : $M$ is a TM and $L(M)$ is decidable} is undecidable

complexity-theory turing-machines decidability

answered Jun 14 at 16:59 Léon 31

1

vote

4

answers

604

views

The Halting problem proof is wrong?

complexity-theory turing-machines computability halting-problem

modified Jun 11 at 20:00 gnasher729 22.7k

2

votes

1

answer

37

views

Does $NP^{SAT}=NP^{NP}$?

complexity-theory turing-machines np oracles

answered Jun 11 at 9:18 Evangelos Bampas 166

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled