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 2 Bountied Hot Week Month

0

votes

1

answer

37

views

Is there a total binary computable function that specifies Turing machines with nonempty domain?

computability

modified 2 hours ago plshelp 191

0

votes

1

answer

19

views

Why there is no Turing Machine that accepts the Diagonal Language?

turing-machines computability

modified yesterday Steven 9,180

0

votes

1

answer

30

views

Confusion of halting problem

computability halting-problem

modified yesterday nir shahar 1,255

1

vote

1

answer

25

views

Prove a language is not recursive enumerable

turing-machines computability rice-theorem

modified yesterday Community♦ 1

0

votes

2

answers

99

views

Decidable questions of undecidable problems

turing-machines computability undecidability

modified 2 days ago plshelp 191

0

votes

0

answers

15

views

Time complexity - Head stay transition - Turing Machine

turing-machines time-complexity computability

modified Jul 5 at 20:34 quetzal94 1

0

votes

1

answer

41

views

Given $n$ unique items and an $m^{th}$ normalised value, compute $m^{th}$ permutation without factorial expansion

algorithms time-complexity computability recurrence-relation permutations

modified Jul 3 at 20:10 NotDijkstra 101

1

vote

1

answer

34

views

What is the theoretical result of flattening a list containing only itself?

computability logic lists

answered Jul 2 at 21:26 nir shahar 1,255

1

vote

0

answers

33

views

How to show that these two disjoint sets $A$ and $B$ exist

turing-machines computability undecidability semi-decidability

asked Jul 1 at 5:48 Link L 387

9

votes

1

answer

103

views

Analogue of the topology-computability correspondence for computational complexity

complexity-theory turing-machines computability semantics topology

answered Jun 30 at 12:07 Arno 1,023

0

votes

1

answer

294

views

A language which is neither r.e. nor co-r.e

turing-machines computability undecidability

modified Jun 30 at 12:06 Community♦ 1

7

votes

4

answers

10k

views

How to determine if an automata (DFA) accepts an infinite or finite language?

formal-languages computability finite-automata

modified Jun 26 at 19:43 6005 2,954

1

vote

0

answers

31

views

What is sideways recursion

computability recursion

asked Jun 26 at 11:36 pinpinokio 111

0

votes

2

answers

111

views

Is $MIN_{TM}$ not in $\overline{RE\cup coRE}$

turing-machines computability reductions

modified Jun 23 at 19:00 Community♦ 1

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled