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

1 answer
0 votes
34 views
Are turing machines & equivalents with infinite sized random programs still turing machines?
1 answer
0 votes
102 views
IS SUBSET-SUM in P if b(the sum) is given in unary and a1,...,an is in binary?
0 answers
1 vote
68 views
Mathematical resource material accompanying TAPL
0 answers
1 vote
15 views
Are there more efficient recognizers for the halting problem?
1 answer
2 votes
33 views
Computable Numbers and Cantor's Diagonal Method
0 answers
0 votes
13 views
Turing machine with polynomial complexity on Jflap
1 answer
0 votes
37 views
How to evaluate all the binary sequences, generated from $2^{100}$ for finding all the sequeces which contain minimum $10$ zeros?
0 answers
-1 votes
16 views
Describe how to build a non-deterministic Turing machine that accepts the set of all element prefixes of $L$, i.e, $PREFIX(L)$
0 answers
-2 votes
28 views
Prove by reduction that the language $L^♦ = \{N | N \text{ is a } TM \text{ and } L(N) \text{ is a recursive language}\}$ is not recursive
1 answer
0 votes
35 views
How Universal Turing Machines can do something if a machine doesn't accept?
0 answers
0 votes
7 views
In the Recursion Theorem, does obtaining a description of SELF increase the length of the program?
1 answer
-1 votes
33 views
Turing machine to find maximum of an infinite set
Browse more Questions