<we><edit> <!-- questions and answers -->
satisfiability
formal-languages
graphs
complexity-classes
computational-geometry
memory-management
sets
pumping-lemma
data-compression
graph-theory
heuristics
computer-networks
lower-bounds
linear-programming
arithmetic
automata
landau-notation
proof-techniques
machine-learning
quantum-computing
regular-expressions
halting-problem
undecidability
algorithm-analysis
computation-models
computability
Simulating Turing Machine with writing only on non-input fields on read-only Turing machine
complexity-theory
computability
turing-machines
How do I develop a structured work method for theoretical computer science?
complexity-theory
formal-languages
computability
Proving or disproving a set of total functions is countable
complexity-theory
computability
proof-techniques
counting
Church-Turing Thesis and computational power of neural networks
computability
turing-machines
church-turing-thesis
Integer Programming Complexity
complexity-theory
computability
Is the number of tests needed to know if a program computes the identity computable?
computability
lambda-calculus
Proof of equivalence of L0 and language accepted by made up machine
computability
turing-machines
Decidability of whether a language described by Turing machine is regular
computability
regular-languages
undecidability
Is {< M >| L(M) ∩ (ab)∗ is infinite} in D, SD/D, or not in SD?
computability
turing-machines
undecidability
Computability of an expression of a function rather than a function itself?
computability
Difference between Non R.E and Co-R.E
computability
turing-machines
The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?
computability
turing-machines
undecidability
rice-theorem
Decidability of whether CFL = RL
computability
formal-grammars
undecidability
decision-problem
Infinite union of regular language
computability
regular-languages
Is it decidable whether the language of a given CFG contains a palindrome?
computability
context-free
undecidability
Can two deterministic turing-machines avoid each other in a sidewalk?
computability
turing-machines
An infinite decidable language that is a subset of $\overline { A_{TM}}$
computability
turing-machines
undecidability
Prove that the coding $\pi_k$ is effective
computability
Using reduction to prove that a given language is not recursively enumerable
computability
turing-machines
enumeration
Decidability of a given language
computability
turing-machines
undecidability
Show a problem using one approach is at least as hard as using another approach
complexity-theory
computability
np-complete
reductions
proof-techniques
4 serial printer to print on one single printer
computability
Computability of a function and decidability
computability
turing-machines
Turing degree incomparable with any countable-ordinal jump of another Turing degree?
computability
turing-machines
How to show that any computable function is bounded above by Busy Beaver Function?
computability
turing-machines
Show that 0^n1^n is decidable
computability
turing-machines
undecidability
pushdown-automata
Why is $\mu$ finite looping?
computability
mu-calculus
If $L$ is recursively enumerable (or recursive) then so is $L′$
formal-languages
computability
reductions
closure-properties
How does it demonstrate that the computational model of rewriting is adequate?
computability
turing-machines
lambda-calculus
computation-models
What is decider?
computability
turing-machines
Can non-recursively enumerable languages be solved with dovetailing?
computability
undecidability
Decidability of the TM's computing a non-empty subset of total functions
computability
turing-machines
reductions
undecidability
Prove ALL$_{\text{TM}}$ is undecidable reduction problem
computability
reductions
undecidability
Proving there exists an infinite number of Turing machines is a decidable problem
computability
turing-machines
Construct a TM for $L = \{ M | M$ is a Turing machine with no useless states}
computability
turing-machines
undecidability
The set of turing machine that stops with input zero is not recursive
computability
rice-theorem
Show $USELESS_{TM}=\{ M | M$ is a Turing machine with at least one useless state$\}$ is recursively enumerable?
computability
turing-machines
undecidability
Showing the predicate $n \leq \sqrt2 < n+1$ is primitive recursive
computability
primitive-recursion
What is the source of uncomputability?
computability
What is the explicit definition about the computablity of non-deterministic Turing machine?
computability
turing-machines
nondeterminism
Given a computable function $f$ and a decidable language $L$, is there a Turing machine $M$ such that $M$ both decides $L$ and computes $f$?
computability
turing-machines
computation-models
Determining if $L(M)=L(M)^r$ is a decidable problem?
computability
turing-machines
undecidability
Maximum value of LOOP-Program turing-computable
computability
loops
check-my-answer
Recursion Tree Analysis by Leaves
computability
asymptotics
recurrence-relation
Is the Language below decidable?
computability
turing-machines
undecidability
decision-problem
Decidability of CFG that accepts at least one odd length string
computability
turing-machines
context-free
Proving that it is undecidable if a Turing machine accepts a language that is its own reverse
computability
turing-machines
decision-problem
Is there an equivalence between "does this program halt" and "is this sentence provable"?
computability
turing-machines
The 'directionality' of reductions?
computability
turing-machines
reductions
halting-problem
Size of the language accepted by a Turing Machine
computability
turing-machines
Will the machine ever reach on any other state other than start state?
computability
Undecidable predicate logic is decidable by people?
computability
logic
undecidability
first-order-logic
logical-validity
Completeness problem of TM
computability
turing-machines
semi-decidability
Complement of halting problem Co-RE or non R.E
computability
halting-problem
Is below language recursive?
computability
turing-machines
Nontrivial examples of sparse languages
complexity-theory
computability
Proving Blank-halt to be recursively enumerable through reduction to Halting problem
computability
turing-machines
reductions
halting-problem
Confusion about reduction of $L=\{w_i | M_i\text{ halts on }w_i\}$ to Halting Problem or Diagonalization language?
computability
reductions
halting-problem
Is the complement of the Turing machine equality language not recursively enumerable as well?
computability
turing-machines
undecidability
Are there unary languages that are in RE but not R?
computability
Turing reduction problem, intersection is equal to an empty set
computability
reductions
Decidability of {(M,w); M terminates on input w and tape of M is empty after computation}
computability
turing-machines
undecidability
semi-decidability
Show that function is not turing-computable?
computability
check-my-answer
Are there noncomputable functions with a finite search space?
computability
Does a Turing Machine with a 2-dimensional tape recognize RE languages?
computability
turing-machines
Prove that { ⟨M⟩ ∣ ⟨M⟩ ∉ L(M) } is undecidable
computability
turing-machines
undecidability
Prove whether this language is (partially) decidable
computability
turing-machines
undecidability
semi-decidability
Construct a computable function from non-computable funciton
computability
Reduce Turing Machine
computability
turing-machines
reductions
Giving a regular expression for a situation of a question
computability
regular-languages
regular-expressions
A two-tape deterministic Turing machine that recognizes an exponential string
computability
turing-machines
Constructing a decider for a language
computability
turing-machines
undecidability
closure-properties
Why are Oracle call instances bounded in the definition of FPT Turing reductions?
algorithms
complexity-theory
graph-theory
computability
parameterized-complexity
Is effective solvability a coherent and/or useful concept?
computability
undecidability
computation-models
What are some undecidable problems for recursive languages?
computability
undecidability
Closure property of recursively enumerable language
computability
closure-properties
A Turing machine recognizing languages of Turing machines
computability
turing-machines
automata
There exist countably many enumerable disjoint and inseparable sets
computability
What Good Is Kolmogorov Complexity Since It Is Relative?
computability
information-theory
randomness
kolmogorov-complexity
Does showing a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?
computability
turing-machines
reductions
undecidability
If $R(x,y)$ is a recursive relation, then $\exists y\leq 2$ such that $R(x,y)$ is recursive
computability
recursion
Given grammar, a nonterminal, and a string, does there exist a parse tree that uses the nonterminal?
computability
context-free
formal-grammars
What do we know about the reciprocal busy beaver series?
computability
turing-machines
busy-beaver
Finding a function which is a mapping reduction of A to B
computability
turing-machines
reductions
If $W$ is a Godel universal set there exists a number $x$ s.t. $Wx=x$
computability
Enumerable disjoint subsets whose union is equal to the union of the sets
computability
semi-decidability
Recursion Theorem : why does $SELF$ need $A$ and $B$ parts?
complexity-theory
computability
turing-machines
Constructible enumerable set
algorithms
computability
turing-machines
enumeration
Decide whether DFA have useless states
computability
finite-automata
Is the equality of two DFAs a decidable problem?
computability
automata
finite-automata
decision-problem
Example of decidable set whose preimage is not decidable
computability
How strong is an countable infinity large circult?
computability
Are there any countable sets that are not computably enumerable?
computability
semi-decidability
Why does the time/space tradeoff exist
computability
optimization
information-theory
Undecidable Problem for Regular Languages
computability
regular-languages
undecidability
Rice's Theorem for Total Computable Functions
computability
rice-theorem
Why is $A \leq_T \bar{A}$?
computability
turing-machines
reductions
Language of Turing machines that never visit some given state
computability
turing-machines
undecidability
NTM's and the halting problem
algorithms
computability
halting-problem
nondeterminism
Show that RE is closed against right-quotient
computability
closure-properties
semi-decidability