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

1

vote

1

answer

56

views

Is it possible to make a Turing Machine that accepts the language $\{\alpha\alpha\alpha | \alpha \in \{a, b\}^∗\}$?

turing-machines

modified 9 hours ago Community♦ 1

0

votes

1

answer

22

views

How to enumerate all Turing machines?

turing-machines enumeration encoding-scheme

modified yesterday Community♦ 1

0

votes

1

answer

61

views

“problematic” non-halting inputs for turing machines

turing-machines semi-decidability

modified yesterday nir shahar 652

-2

votes

0

answers

15

views

Elements of Theory of Computation 2nd Turing Machine

turing-machines

asked yesterday Array 1

1

vote

2

answers

190

views

To what extent is an x86 machine equivalent to a Turing Machine?

turing-machines turing-completeness church-turing-thesis

modified 2 days ago polcott 119

1

vote

1

answer

24

views

How does an enumerator for machines for languages work?

turing-machines enumeration

modified 2 days ago Yuval Filmus 226k

0

votes

1

answer

16

views

How do you represent an r.e. complexity class with a list of TMs?

complexity-theory turing-machines enumeration

answered May 30 at 20:04 nir shahar 652

0

votes

1

answer

16

views

Can a DTM simulate an enumerator E?

turing-machines enumeration

modified May 30 at 17:00 Steven 7,470

0

votes

1

answer

38

views

Check if language is decidable

formal-languages turing-machines undecidability semi-decidability

modified May 28 at 23:32 nir shahar 652

2

votes

1

answer

47

views

Expressing functions using the arithmetic dictionary

turing-machines computation-models first-order-logic

answered May 28 at 22:58 Beleg 182

2

votes

1

answer

122

views

Combining 2 problems in NP into one

complexity-theory turing-machines np decision-problem oracle-machines

answered May 28 at 11:05 Yuval Filmus 226k

0

votes

1

answer

105

views

Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem.

turing-machines automata halting-problem

modified May 28 at 8:06 Community♦ 1

1

vote

3

answers

41

views

What does “Every CFL is decidable” exactly mean?

turing-machines automata context-free undecidability decision-problem

answered May 28 at 1:04 Jake 3,479

1

vote

1

answer

22

views

Is reaching in less lines semi-decidable?

turing-machines semi-decidability

modified May 27 at 18:12 Yuval Filmus 226k

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled