User Denis

45 votes

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

answered Apr 19, 2016 at 10:07

32 votes

What is the smallest Turing machine where it is unknown if it halts or not?

answered Feb 11, 2014 at 13:00

29 votes

Most important new papers in computational complexity

answered Jun 24, 2019 at 13:55

18 votes

Theoretical Computer Science vs other Sciences?

answered Mar 14 at 0:01

14 votes

Accepted

Parameterized complexity of inclusion of regular languages

answered Feb 23, 2018 at 12:37

14 votes

What notable automaton models have polynomially-decidable containment?

answered Jun 17, 2014 at 15:07

13 votes

A simple decision problem whose decidability is not known

answered Sep 4, 2013 at 10:12

13 votes

Counterintuitive results for undergraduates

answered May 27, 2015 at 13:49

12 votes

Are Boolean circuits 'universal'

answered Sep 12, 2013 at 12:34

12 votes

Caterpillar decomposition of trees

answered Mar 7, 2013 at 17:14

11 votes

Accepted

On the realisation of monoids as syntactic monoids of languages

answered Jun 9, 2016 at 19:46

10 votes

Accepted

Deterministic Büchi + its complement covers LTL?

answered Apr 25, 2013 at 18:57

10 votes

Accepted

How to acknowledge answers of TCS in the paper?

answered Jul 7, 2021 at 10:30

9 votes

Complexity of Unknotting problems

answered Jan 29, 2021 at 9:43

9 votes

Accepted

Proof and computational complexity

answered Apr 17, 2021 at 12:15

9 votes

Accepted

For a specific unbounded Turing machine, is its Halting problem undecidable?

answered May 22, 2018 at 11:26

8 votes

Constraints on sliding windows

answered Nov 19, 2019 at 17:01

8 votes

Major unsolved problems in theoretical computer science?

answered Jul 23, 2014 at 9:16

8 votes

Accepted

Is coRE closed under concatenation?

answered Jul 6, 2021 at 15:35

7 votes

Accepted

Is the function $f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)$ regularity-preserving?

answered Apr 15, 2021 at 22:02

7 votes

Accepted

star height of star-free languages

answered Oct 18, 2021 at 21:58

7 votes

Are regular expressions inherently more difficult to construct than DFAs for humans?

answered Jan 4 at 16:40

7 votes

Accepted

The theoretical complexity of Go - The state of the art

answered Mar 26, 2020 at 0:39

7 votes

Accepted

Kleene Algebra for star-free regular expressions

answered Apr 23, 2020 at 14:22

7 votes

Stephen Hawking's impact on computer science

answered Mar 15, 2018 at 15:09

6 votes

Accepted

NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?

answered Apr 19, 2017 at 15:00

6 votes

NP-complete decision problems on deterministic automata

answered Mar 3, 2020 at 11:58

6 votes

Accepted

Example of a $U^\omega$ that is not Deterministic Büchi recognizable

answered Aug 19, 2014 at 17:14

6 votes

Are there any schools with researchers interested in cellular automata?

answered Dec 8, 2014 at 9:42

6 votes

What hierarchies and/or hierarchy theorems do you know?

answered Feb 2, 2014 at 14:32

Stack Exchange Network

94 Answers

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

What is the smallest Turing machine where it is unknown if it halts or not?

Most important new papers in computational complexity

Theoretical Computer Science vs other Sciences?

Parameterized complexity of inclusion of regular languages

What notable automaton models have polynomially-decidable containment?

A simple decision problem whose decidability is not known

Counterintuitive results for undergraduates

Are Boolean circuits 'universal'

Caterpillar decomposition of trees

On the realisation of monoids as syntactic monoids of languages

Deterministic Büchi + its complement covers LTL?

How to acknowledge answers of TCS in the paper?

Complexity of Unknotting problems

Proof and computational complexity

For a specific unbounded Turing machine, is its Halting problem undecidable?

Constraints on sliding windows

Major unsolved problems in theoretical computer science?

Is coRE closed under concatenation?

Is the function $f(a_1 \dotsm a_n) = a_1(a_1a_2)(a_1a_2a_3)\ \dotsm\ (a_1 \dotsm a_n)$ regularity-preserving?

star height of star-free languages

Are regular expressions inherently more difficult to construct than DFAs for humans?

The theoretical complexity of Go - The state of the art

Kleene Algebra for star-free regular expressions

Stephen Hawking's impact on computer science

NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?

NP-complete decision problems on deterministic automata

Example of a $U^\omega$ that is not Deterministic Büchi recognizable

Are there any schools with researchers interested in cellular automata?

What hierarchies and/or hierarchy theorems do you know?