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
Computer Science

Explore our Questions

Ask Question
more tags
Active 4 Bountied Hot Week Month
1 answer
0 votes
34 views
Are turing machines & equivalents with infinite sized random programs still turing machines?
nir shahar
  • 10.3k
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?
Community Bot
  • 1
0 answers
1 vote
68 views
Mathematical resource material accompanying TAPL
Discrete lizard ♦
  • 6,930
0 answers
1 vote
15 views
Are there more efficient recognizers for the halting problem?
zyl1024
  • 442
1 answer
2 votes
33 views
Computable Numbers and Cantor's Diagonal Method
Zhiltsoff Igor
  • 146
0 answers
0 votes
13 views
Turing machine with polynomial complexity on Jflap
Luigi Daddario
  • 1
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?
gnasher729
  • 24.4k
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)$
MaxUr
  • 1
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
Massimo2015MX
  • 5
1 answer
0 votes
35 views
How Universal Turing Machines can do something if a machine doesn't accept?
Nathaniel
  • 5,123
0 answers
0 votes
7 views
In the Recursion Theorem, does obtaining a description of SELF increase the length of the program?
Garrick White
  • 33
1 answer
-1 votes
33 views
Turing machine to find maximum of an infinite set
6005
  • 5,005
Browse more Questions

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.