Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up

Here's how it works:

Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top

Explore Our Questions

active 2 featured hot week month

more tags

-3

votes

answer

153

views

Is Alan Turing's proof of the incomputability of halting problem invalid?

computability halting-problem mathematical-foundations

modified yesterday Apass.Jack 727

votes

answer

views

Are all terms of type forall a. a operationally bottom?

computability type-theory

answered Aug 11 at 13:46 chi 9,773

votes

answer

views

Any common problems solvable by DFA/NFA or PDA except recognizing languages?

formal-languages computability automata

modified Aug 8 at 9:00 Community♦ 1

vote

answers

112

views

Can hypercomputation compute all kinds of incomputable numbers/functions/problems…etc?

computability quantum-computing hypercomputation

answered Aug 7 at 1:41 Aryeh 126

votes

answer

views

Connecting strings in a graph is a PSPACE problem

complexity-theory computability space-complexity

modified Aug 3 at 14:01 Community♦ 1

votes

answer

views

If $\overline{M}$ is recursively enumerable and $A$ is recursive, what could we say about $A \cap M$?

computability

answered Jul 31 at 20:04 Noah Schweber 433

votes

answers

views

Proof that total computable functions are not enumerable

computability semi-decidability enumeration

answered Jul 29 at 21:38 Noah Schweber 433

vote

answer

views

Prove that $D =\{x \in \mathbb{N} | \Phi_x(x)\uparrow\}$ is not recursively enumerable

computability proof-techniques

answered Jul 29 at 18:49 Noah Schweber 433

vote

answer

views

Prove that $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ is partial recursive

computability proof-techniques

modified Jul 28 at 21:50 Yuval Filmus 180k

votes

answer

views

Can a PDA guess more than once? L = {aⁿ bⁱ aⁿ | i,n > 0 }

computability

modified Jul 27 at 15:01 Community♦ 1

vote

answer

views

Prove or disprove if $L_{1}$ is Turing-recognizable and $L_{2}$ is co-Turing-recognizable then $L_{1}\cap L_{2}$ is decidable

turing-machines computability

modified Jul 27 at 10:02 xskxzr 2,551

vote

answers

views

Understanding proof for Busy Beaver being uncomputable

computability turing-machines halting-problem busy-beaver

modified Jul 24 at 13:44 James Parker 21

votes

answers

335

views

Decidability of the TM's computing a non-empty subset of total functions

computability turing-machines reductions undecidability

modified Jul 22 at 11:07 Community♦ 1

votes

answer

views

Are there any implementations of computability logic?

computability logic

answered Jul 20 at 18:46 Lance Pollard 801

Browse More Questions

Stack Exchange Network

current community

your communities

more stack exchange communities

Explore Our Questions

Is Alan Turing's proof of the incomputability of halting problem invalid?

Are all terms of type forall a. a operationally bottom?

Any common problems solvable by DFA/NFA or PDA except recognizing languages?

Can hypercomputation compute all kinds of incomputable numbers/functions/problems…etc?

Connecting strings in a graph is a PSPACE problem

If $\overline{M}$ is recursively enumerable and $A$ is recursive, what could we say about $A \cap M$?

Proof that total computable functions are not enumerable

Prove that $D =\{x \in \mathbb{N} | \Phi_x(x)\uparrow\}$ is not recursively enumerable

Prove that $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ is partial recursive

Can a PDA guess more than once? L = {aⁿ bⁱ aⁿ | i,n > 0 }

Prove or disprove if $L_{1}$ is Turing-recognizable and $L_{2}$ is co-Turing-recognizable then $L_{1}\cap L_{2}$ is decidable

Understanding proof for Busy Beaver being uncomputable

Decidability of the TM's computing a non-empty subset of total functions

Are there any implementations of computability logic?

Hot Network Questions