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 Hot Week Month

2

votes

1

answer

38

views

is there a constructive proof of the existence of a language which isn't recursive (without invoking infinities)?

turing-machines semi-decidability

modified 2 hours ago Arno 1,233

1

vote

1

answer

17

views

1-Tape Non-deterministic Turing machine and non-palindromes

turing-machines decision-problem

answered 7 hours ago A.M. 254

1

vote

1

answer

29

views

Explain the simulation of an if else statement in LOOP

turing-machines proof-techniques correctness-proof loops simulation

answered yesterday Yuval Filmus 242k

0

votes

1

answer

27

views

Where is the problem in this proof that deciders are no stronger than LBAs?

complexity-theory turing-machines

modified 2 days ago Community♦ 1

2

votes

1

answer

44

views

this language and acceptance by queue automaton

turing-machines automata nondeterminism

answered Jan 22 at 5:18 Hendrik Jan 24.4k

0

votes

1

answer

60

views

Copy operation in under 9 states?

finite-automata turing-machines

modified Jan 21 at 17:07 Community♦ 1

1

vote

1

answer

22

views

A language is decidable iff it is Turing-recognizable and co-Turing-recognizable (WHY?)

turing-machines computability undecidability

answered Jan 21 at 15:36 Pål GD 9,116

1

vote

0

answers

26

views

Correct terminology for $P1;P2$?

turing-machines terminology loops

asked Jan 20 at 18:38 Ski Mask 413

0

votes

1

answer

34

views

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

turing-machines rice-theorem

answered Jan 20 at 16:51 MikeChav 11

0

votes

0

answers

24

views

Is my assumption about non trivial propery correct?

turing-machines computability rice-theorem

asked Jan 20 at 14:38 user6394019 179

0

votes

1

answer

28

views

Single tape Turing Machine that accepts string with at least five G's and at most three T's?

turing-machines

answered Jan 20 at 7:58 Numbra 121

0

votes

1

answer

42

views

Is a language recursive? 2 wrong ways of solving

complexity-theory formal-languages turing-machines computability

modified Jan 19 at 13:34 VashTheStampede 121

0

votes

1

answer

29

views

If $A$ reduces to $B$ and $B$ is NP-hard, is $A$ NP-hard?

algorithms complexity-theory turing-machines computability np-complete

modified Jan 18 at 21:16 Yuval Filmus 242k

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled