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

2

votes

3

answers

15

views

Can a Non-Deterministic Pushdown Automata recognize $ \# a^nb^{2^n} \# $ which a TM can?

turing-machines pushdown-automata

modified 52 mins ago bluewander 21

1

vote

0

answers

9

views

Proof that $(L_{all})^C$ is not recursively enumerable

complexity-theory turing-machines

modified 8 hours ago David 11

55

votes

7

answers

12k

views

Are there minimum criteria for a programming language being Turing complete?

computability programming-languages turing-machines turing-completeness

answered 15 hours ago Keiji Matsui 1

1

vote

1

answer

46

views

Undecidable: $w$ on which a TM M $M$ halts after $\leq w$ steps

turing-machines undecidability

modified 2 days ago Community♦ 1

4

votes

1

answer

720

views

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

turing-machines simulation computation-models

modified Dec 5 at 19:02 Community♦ 1

0

votes

1

answer

52

views

Some questions about the Computability of Turing Machines

turing-machines church-turing-thesis

modified Dec 5 at 16:03 Aaron Rotenberg 499

1

vote

0

answers

26

views

Is ASM a regular language?

formal-languages turing-machines context-free regular-expressions

Dec 5 at 14:20 Erotemic 111

2

votes

1

answer

64

views

If A and B are NP-complete, then A ∪ B need not be NP-complete

turing-machines np-complete np nondeterminism

modified Dec 4 at 17:57 narek Bojikian 2,210

0

votes

1

answer

25

views

On the computable function of a problem that halts

turing-machines computability halting-problem

modified Dec 4 at 6:01 Community♦ 1

0

votes

1

answer

15

views

Design a Turing machine that accepts L={ww^r | w:(0,1)*}?

turing-machines

Dec 4 at 4:25 Katie Rose 25

2

votes

0

answers

51

views

Converting from m base to n base without arithmetic operations (Where m<n )

turing-machines base-conversion

modified Dec 3 at 2:37 Fabio Palm 21

0

votes

0

answers

17

views

Prove undecidability of a TM M that accepts at least one input AND rejects at least one input

turing-machines

modified Dec 1 at 23:07 Artur Rossi 1

2

votes

0

answers

22

views

Bounds on tape alphabet size of a Turing Machine encoding

complexity-theory turing-machines

modified Dec 1 at 14:43 Oren 165

0

votes

0

answers

15

views

Correct Turing machine representation for Rice Theorem proof

turing-machines undecidability rice-theorem

asked Nov 30 at 19:11 Gianni Spear 187

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled