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

Ask Question

more tags

Active 3 Bountied Hot Week Month

3

votes

2

answers

53

views

How can I compute logarithm when comparison is undecidable?

algorithms computability numerical-algorithms numerical-analysis

answered 16 hours ago gnasher729 20.1k

1

vote

2

answers

1k

views

Show that the single-tape TMs that can not write on the portion the portion of the tape containing the input string recognize only regular languages

complexity-theory turing-machines computability

modified yesterday xdavidliu 308

3

votes

3

answers

2k

views

Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs

turing-machines computability decision-problem

modified Sep 21 at 18:23 xdavidliu 308

1

vote

2

answers

30

views

Do languages in $\mathsf{coRE} \setminus \mathsf{R}$ have Turing machines?

turing-machines computability

answered Sep 19 at 20:20 Noah Schweber 1,886

1

vote

2

answers

24

views

Can you say anything interesting about a language knowing only that it is prefix-closed?

complexity-theory formal-languages computability

modified Sep 17 at 23:11 Yuval Filmus 232k

1

vote

1

answer

20

views

Proof that languages are Turing-recognizable iff computably-enumerable

formal-languages turing-machines computability enumeration

modified Sep 17 at 16:29 Yuval Filmus 232k

5

votes

2

answers

446

views

Decidability of dependent typing on primitive recursive languages

computability undecidability type-checking dependent-types primitive-recursion

modified Sep 16 at 4:32 ComFreek 332

0

votes

0

answers

22

views

Which function results from primitive recursion of the functions g and h?

computability recursion primitive-recursion

asked Sep 9 at 9:54 Doesbaddel 148

6

votes

0

answers

503

views

What could we say about that conjecture that yields P != NP?

algorithms complexity-theory graphs computability np-complete

modified Sep 8 at 20:57 Dudi Frid 121

46

votes

12

answers

13k

views

Is C actually Turing-complete?

computability turing-completeness c

modified Sep 7 at 3:13 polcott 149

0

votes

1

answer

62

views

In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?

complexity-theory computability automata finite-automata computation-models

modified Sep 5 at 5:01 Community♦ 1

1

vote

1

answer

47

views

Why, intuitively, does the Ackermann function require $\mu$-minimisation?

computability recursion

modified Sep 2 at 19:42 Yuval Filmus 232k

2

votes

1

answer

32

views

algorithm for checking satisfiability

complexity-theory computability np satisfiability 3-sat

answered Aug 28 at 11:13 plshelp 607

1

vote

1

answer

61

views

Church–Turing thesis and infinite Turing machines

turing-machines computability

modified Aug 28 at 6:26 Yuval Filmus 232k

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled