Explore Our Questions

more tags

Active 2 Featured Hot Week Month

7

votes

6

answers

934

views

How is Turing's Solution to the Halting Problem Not Simply “Failure By Design”?

computability halting-problem

modified 7 hours ago jmoreno 143

1

vote

0

answers

15

views

How do you prove that $A = \{ x \in \mathbb{N} | W_{x} = [0..x]\}$ is a productive set through functional reduction?

computability

modified 7 hours ago NetHacker 116

1

vote

2

answers

30

views

Would any continuous model of the universe have/be based on hypercomputational laws?

computability undecidability computation-models church-turing-thesis hypercomputation

modified 20 hours ago Andrej Bauer 20.2k

0

votes

2

answers

60

views

Proving a language as undecidable without using reductions

turing-machines computability undecidability

modified 2 days ago Raphael♦ 57.7k

1

vote

1

answer

39

views

How does one use the Nerode-Myhill theorem to prove that a language is regular?

complexity-theory computability regular-languages

modified Feb 20 at 1:56 Apass.Jack 11.5k

36

votes

1

answer

24k

views

Is a push-down automaton with two stacks equivalent to a turing machine?

computability turing-machines automata pushdown-automata

modified Feb 18 at 15:33 Raphael♦ 57.7k

1

vote

1

answer

26

views

Recognizer to check if the language of a Turing machine contains a finite subset

turing-machines computability

answered Feb 17 at 5:32 xskxzr 3,575

2

votes

2

answers

60

views

Is determining if a Turing machine runs in constant time decidable if one assumes it halts?

computability time-complexity undecidability halting-problem

modified Feb 14 at 19:06 Tomer Aberbach 128

2

votes

1

answer

44

views

Can generalized Turing machines compute all reals?

turing-machines computability real-numbers hypercomputation

modified Feb 14 at 12:33 Yuval Filmus 193k

6

votes

1

answer

36

views

Proving a set is at a certain level of the arithmetical hierarchy

complexity-theory computability

modified Feb 14 at 11:44 Yuval Filmus 193k

0

votes

0

answers

22

views

Church-Turing thesis and hypercomputation?

turing-machines computability church-turing-thesis hypercomputation

modified Feb 10 at 4:16 Yuval Filmus 193k

0

votes

1

answer

104

views

Prove that there exists a machine which decides an infinite subset of halting problem

computability turing-machines halting-problem

modified Feb 7 at 15:01 Community♦ 1

1

vote

1

answer

33

views

A language which is neither r.e. nor co-r.e

turing-machines computability undecidability

modified Feb 6 at 10:22 Upc 116

7

votes

1

answer

5k

views

What is the difference between decidability and computability?

computability terminology

modified Jan 31 at 12:55 lalilulelost 1

Browse More Questions

Computer Science Stack Exchange works best with JavaScript enabled