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

2 votes
1 answer
33 views

Upper bound on output of halting transducer

4 votes
1 answer
224 views

Are any "standard" complexity classes uncountably infinite?

0 votes
0 answers
26 views

Help understanding the proof that $L = \{ \langle M \rangle \mid M \text{ is a TM that accepts the input string } 101\}$ is undecidable

0 votes
1 answer
93 views

Why can't humans translate all of their abilities into an algorithm? Will that hold true in the future?

0 votes
1 answer
39 views

Computability = Enumerating a sequence in the particular order?

0 votes
1 answer
316 views

Can a PDA guess more than once? L = {aⁿ bⁱ aⁿ | i,n > 0 }

0 votes
1 answer
1k views

Turing machine that recognizes the language $\{a^{n}b^{2n}c^{3n}|\ n\ge0\}$

3 votes
1 answer
110 views

For which values of $k$ is a $k$-state-bounded version of the halting problem decidable?

0 votes
1 answer
118 views

Determining recursive enumerability of given languages

0 votes
0 answers
19 views

Does valid value in L2 have to be gotten from L1 when we have a Many-One Reduction from L1 to L2

0 votes
1 answer
30 views

Can an unreocognizable language be Turing-reducible to a recognizable language?

1 vote
1 answer
35 views

function is computable iff its graph is recursively enumerable?

-1 votes
0 answers
32 views

Is it possible to compute the differentiation of any differentiable function on an interval?

1 vote
1 answer
52 views

If the Navier-Stokes equations problem is a computable problem, for example a set/language called "L", what are the elements of L?

Browse more Questions