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

2

answers

37

views

Busy-Beaver-like question for WHILE-Programs (Theoretical CS)

computability halting-problem busy-beaver

answered 18 hours ago vonbrand 9,509

-1

votes

1

answer

36

views

Are non halting programs not computable?

computability halting-problem

answered 19 hours ago vonbrand 9,509

1

vote

5

answers

2k

views

Whether TM accepts epsilon?

turing-machines computability

modified Jan 22 at 8:41 reinierpost 3,590

0

votes

1

answer

28

views

What computational model supports arbitrarily sized integers?

turing-machines computability integers primes factoring

answered Jan 21 at 0:53 D.W.♦ 115k

0

votes

0

answers

27

views

Union of a decidable language with complement of a recursively enumerable language

turing-machines computability

modified Jan 19 at 2:16 Blitz Mee 31

0

votes

1

answer

35

views

Can a computable program have an infinite output?

computability

answered Jan 18 at 21:02 D.W.♦ 115k

-1

votes

1

answer

21

views

if there is no reduction from A to B

computability reductions

modified Jan 18 at 15:18 narek Bojikian 3,176

3

votes

0

answers

95

views

Undecidability of language involving two TMs

turing-machines computability undecidability

modified Jan 18 at 10:25 xskxzr 5,796

0

votes

0

answers

26

views

Use the Rice's theorem to prove that the following property of a Recursive Enumerable language L is undecidable

complexity-theory computability rice-theorem

asked Jan 17 at 14:35 noisecape 1

3

votes

1

answer

113

views

Compare two complexity functions having the same asymptotic complexity

complexity-theory time-complexity computability master-theorem

modified Jan 14 at 14:08 entropyfeverone 26

0

votes

1

answer

29

views

Would models of computation in other conceivable universes be Turing complete?

computability computation-models physics

answered Jan 9 at 17:34 Noah Schweber 1,383

0

votes

0

answers

16

views

Proof by reduction that the Universal Language is not recursive using the complement of the Diagonalization language

turing-machines computability reductions

asked Jan 8 at 14:06 michafranz 1

0

votes

1

answer

37

views

Are Turing unrecognizable and undecidable languages, recognized and decided by hyper computation?

turing-machines computability church-turing-thesis hypercomputation

modified Jan 7 at 23:13 Aaron Rotenberg 1,960

6

votes

3

answers

930

views

Would creating a complete computer simulation of the human brain prove the Church-Turing thesis?

computability simulation church-turing-thesis

modified Jan 5 at 23:59 Libby Chang 1

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled