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

0

votes

3

answers

6k

views

ETM Undecidability

computability turing-machines reductions undecidability

modified 1 hour ago user326210 468

0

votes

2

answers

87

views

Can the intersection two non-recursive sets be recursive? Prove it

turing-machines computability

modified 1 hour ago CommunityBot 1

0

votes

1

answer

295

views

reduction from ALLTM to ETM

turing-machines reductions undecidability proof-techniques

answered 2 hours ago user326210 468

0

votes

0

answers

6

views

Turing Machine that accepts L(M1) = {x^n y^2n z^n | n ∈ N}

formal-languages turing-machines computability

asked 5 hours ago Code.vc 1

0

votes

3

answers

185

views

How it's possible decide CNF by having a turing machine that decide SAT?

algorithms complexity-theory formal-languages turing-machines automata

modified 10 hours ago Daniel Wagner 1,219

1

vote

0

answers

12

views

Proving set of register machines that halt before k steps for some input is non-recursive

turing-machines computability logic undecidability

asked 18 hours ago jack 11

0

votes

1

answer

88

views

Determining recursive enumerability of given languages

formal-languages turing-machines computability formal-grammars

modified 22 hours ago CommunityBot 1

1

vote

2

answers

2k

views

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

complexity-theory turing-machines computability

modified yesterday kne 2,039

0

votes

0

answers

19

views

Is there any problems with equating Turing Machines with Algorithms and Language with Problems?

complexity-theory formal-languages turing-machines definitions decidability

asked 2 days ago Eldacar Hyarmendacil 101

2

votes

2

answers

97

views

Mathematical models of computation that capture more advanced OS and CPU design features

turing-machines reference-request operating-systems computation-models cpu

modified 2 days ago Shashank V M 349

0

votes

1

answer

20

views

Turing machine accepting square

turing-machines data-structures

modified 2 days ago Nathaniel 4,375

1

vote

1

answer

913

views

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

turing-machines undecidability

modified 2 days ago CommunityBot 1

0

votes

2

answers

76

views

Undecidability of TMs recognizing a decidable language

turing-machines undecidability

modified Nov 24 at 12:39 user326210 468

3

votes

1

answer

119

views

Undecidability of language involving two TMs

turing-machines computability undecidability

modified Nov 24 at 5:35 user326210 468

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled