Skip to main content

Explore our questions

0 votes
0 answers
20 views

Proving that if semidecidable, then computable

-1 votes
1 answer
23 views

Create a cfg for the language L = {w ∈ {a,b,c}* : |w| = 3na(w)}

1 vote
2 answers
338 views

A decidable language that can't be decided by a circuit ensemble of linear size

1 vote
2 answers
657 views

IS SUBSET-SUM in P if b(the sum) is given in unary and a1,...,an is in binary?

62 votes
14 answers
24k views

Is C actually Turing-complete?

1 vote
0 answers
31 views

Why does ISA includes instruction for logical operation?

0 votes
1 answer
117 views

How to prove that $L_{D}\leq L_{U}$?

0 votes
1 answer
122 views

Analog computers more powerful than turing machines?

9 votes
14 answers
8k views

Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?

0 votes
1 answer
472 views

Reduction of Turing-machine language

3 votes
1 answer
44 views

Computability- relationship between R, coRE and RE

0 votes
1 answer
50 views

Why Does Computable Analysis Use Type 2 Turing Machines Over Type 1 TM's?

71 votes
7 answers
21k views

Are there minimum criteria for a programming language being Turing complete?

3 votes
2 answers
2k views

Decidability of the language that accepts a universal turing machine

Browse more Questions