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

more tags

Active 2 Bountied Hot Week Month

0

votes

0

answers

13

views

Which of the following languages a decidable?

turing-machines undecidability

asked 2 hours ago jakaa 1

0

votes

1

answer

22

views

A condition for $\emptyset \neq S\subset RE$ under which $L_S \notin RE$

turing-machines computability reference-request

modified 7 hours ago dkaeae 4,255

1

vote

1

answer

57

views

How to prove $L \notin \texttt{DSPACE}(f)$

complexity-theory turing-machines reductions proof-techniques space-complexity

modified yesterday Community♦ 1

4

votes

3

answers

428

views

Decidability of the TM's computing a non-empty subset of total functions

computability turing-machines reductions undecidability

modified Aug 17 at 3:13 xskxzr 4,841

1

vote

0

answers

15

views

Deterministic Time Hierachy Proof by Arora and Barak: Question about time to simulate Turing Machine $M$ that decides separating language

complexity-theory turing-machines time-complexity

asked Aug 12 at 15:24 csstundent 23

2

votes

0

answers

19

views

On teaching Kolmogorov complexity with Python and the complexity of composed strings

turing-machines kolmogorov-complexity python

asked Aug 12 at 12:35 Rami Luisto 11

1

vote

1

answer

39

views

What is an example of a Turing-recognizable infinite word, which is not Turing-decidable?

formal-languages turing-machines

modified Aug 11 at 3:39 rici 5,268

0

votes

1

answer

21

views

Proving whether an input sequence is in a given RE language

turing-machines computability

answered Aug 9 at 13:39 David Richerby 74.7k

2

votes

0

answers

38

views

How strong is an oracle that avoid don't-halt

turing-machines computability oracle-machines

modified Aug 8 at 15:51 l4m2 134

6

votes

1

answer

42

views

What publication first introduced the concept of a non-deterministic Turing machine?

turing-machines reference-request nondeterminism

modified Aug 8 at 11:09 dkaeae 4,255

4

votes

1

answer

662

views

How to simulate a bidirectional TM on a regular one with time factor four?

turing-machines simulation computation-models

modified Aug 7 at 18:02 Community♦ 1

1

vote

1

answer

23

views

How to detect infinite loop exist in linear bounded automata (LBA)?

turing-machines computability undecidability

modified Aug 7 at 14:41 dkaeae 4,255

0

votes

2

answers

115

views

Problem with proving the undecidability of REGULAR$_{TM}$

turing-machines computability reductions

answered Aug 7 at 8:26 Anonemous 24

1

vote

1

answer

17

views

Differences between ALLTM and INF

complexity-theory turing-machines reductions undecidability

answered Aug 7 at 7:20 Yuval Filmus 206k

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled