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

0 votes
0 answers
5 views

is this a contradiction? "stating there are an infinite number of programs but that a program cannot be infinitely long is a contradiction"

1 vote
6 answers
2k views

David Deutsch says "number of atoms in universe is finite", but then says "number of programs of all finite lengths is infinite". Contradiction?

2 votes
1 answer
34 views

Upper bound on output of halting transducer

1 vote
1 answer
35 views

If A U B and A ∩ B are recognizable, then is one of A, A', B, B' also recognizable?

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?

-1 votes
2 answers
322 views

What are the practical examples of Semidecidable problems? Is NP problem a semidecidable problem?

1 vote
1 answer
57 views

Is the set of instances of PCP, which have a solution, semi-decidable?

2 votes
1 answer
2k views

How would a Turing Machine recognize n consecutive characters

0 votes
0 answers
14 views

"Transforming" a Turing machine into another turing machine

0 votes
0 answers
62 views

Designing a Turing machine (TM) to multiply a unary number by 2

1 vote
1 answer
20 views

How is $\mathsf{RP\cap UP}$ not a class containing only unsatisfying languages?

0 votes
0 answers
23 views

Proving $A_{TM}$ is mapping reducible to certain language

0 votes
1 answer
70 views

Prove/disprove that if $L_1, L_2\in RE$ then $L_1-\ L_2, L_1 - \bar{L_2}\in RE$

Browse more Questions