computability

  1. Simulating Turing Machine with writing only on non-input fields on read-only Turing machine

  2. How do I develop a structured work method for theoretical computer science?

  3. Proving or disproving a set of total functions is countable

  4. Church-Turing Thesis and computational power of neural networks

  5. Integer Programming Complexity
  6. Is the number of tests needed to know if a program computes the identity computable?
  7. Proof of equivalence of L0 and language accepted by made up machine

  8. Decidability of whether a language described by Turing machine is regular
  9. Is {< M >| L(M) ∩ (ab)∗ is infinite} in D, SD/D, or not in SD?
  10. Computability of an expression of a function rather than a function itself?
  11. Difference between Non R.E and Co-R.E
  12. The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?
  13. Decidability of whether CFL = RL

  14. Infinite union of regular language
  15. Is it decidable whether the language of a given CFG contains a palindrome?
  16. Can two deterministic turing-machines avoid each other in a sidewalk?

  17. An infinite decidable language that is a subset of $\overline { A_{TM}}$
  18. Prove that the coding $\pi_k$ is effective

  19. Using reduction to prove that a given language is not recursively enumerable
  20. Decidability of a given language

  21. Show a problem using one approach is at least as hard as using another approach

  22. 4 serial printer to print on one single printer

  23. Computability of a function and decidability
  24. Turing degree incomparable with any countable-ordinal jump of another Turing degree?
  25. How to show that any computable function is bounded above by Busy Beaver Function?

  26. Show that 0^n1^n is decidable
  27. Why is $\mu$ finite looping?

  28. If $L$ is recursively enumerable (or recursive) then so is $L′$

  29. How does it demonstrate that the computational model of rewriting is adequate?

  30. What is decider?
  31. Can non-recursively enumerable languages be solved with dovetailing?
  32. Decidability of the TM's computing a non-empty subset of total functions
  33. Prove ALL$_{\text{TM}}$ is undecidable reduction problem
  34. Proving there exists an infinite number of Turing machines is a decidable problem

  35. Construct a TM for $L = \{ M | M$ is a Turing machine with no useless states}

  36. The set of turing machine that stops with input zero is not recursive
  37. Show $USELESS_{TM}=\{ M | M$ is a Turing machine with at least one useless state$\}$ is recursively enumerable?
  38. Showing the predicate $n \leq \sqrt2 < n+1$ is primitive recursive

  39. What is the source of uncomputability?
  40. What is the explicit definition about the computablity of non-deterministic Turing machine?
  41. 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$?

  42. Determining if $L(M)=L(M)^r$ is a decidable problem?

  43. Maximum value of LOOP-Program turing-computable

  44. Recursion Tree Analysis by Leaves
  45. Is the Language below decidable?

  46. Decidability of CFG that accepts at least one odd length string

  47. Proving that it is undecidable if a Turing machine accepts a language that is its own reverse
  48. Is there an equivalence between "does this program halt" and "is this sentence provable"?

  49. The 'directionality' of reductions?

  50. Size of the language accepted by a Turing Machine
  51. Will the machine ever reach on any other state other than start state?

  52. Undecidable predicate logic is decidable by people?
  53. Completeness problem of TM

  54. Complement of halting problem Co-RE or non R.E

  55. Is below language recursive?

  56. Nontrivial examples of sparse languages

  57. Proving Blank-halt to be recursively enumerable through reduction to Halting problem
  58. Confusion about reduction of $L=\{w_i | M_i\text{ halts on }w_i\}$ to Halting Problem or Diagonalization language?

  59. Is the complement of the Turing machine equality language not recursively enumerable as well?

  60. Are there unary languages that are in RE but not R?

  61. Turing reduction problem, intersection is equal to an empty set

  62. Decidability of {(M,w); M terminates on input w and tape of M is empty after computation}

  63. Show that function is not turing-computable?
  64. Are there noncomputable functions with a finite search space?
  65. Does a Turing Machine with a 2-dimensional tape recognize RE languages?

  66. Prove that { ⟨M⟩ ∣ ⟨M⟩ ∉ L(M) } is undecidable
  67. Prove whether this language is (partially) decidable
  68. Construct a computable function from non-computable funciton

  69. Reduce Turing Machine

  70. Giving a regular expression for a situation of a question

  71. A two-tape deterministic Turing machine that recognizes an exponential string
  72. Constructing a decider for a language

  73. Why are Oracle call instances bounded in the definition of FPT Turing reductions?
  74. Is effective solvability a coherent and/or useful concept?

  75. What are some undecidable problems for recursive languages?

  76. Closure property of recursively enumerable language

  77. A Turing machine recognizing languages of Turing machines

  78. There exist countably many enumerable disjoint and inseparable sets

  79. What Good Is Kolmogorov Complexity Since It Is Relative?

  80. Does showing a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?
  81. If $R(x,y)$ is a recursive relation, then $\exists y\leq 2$ such that $R(x,y)$ is recursive

  82. Given grammar, a nonterminal, and a string, does there exist a parse tree that uses the nonterminal?
  83. What do we know about the reciprocal busy beaver series?

  84. Finding a function which is a mapping reduction of A to B

  85. If $W$ is a Godel universal set there exists a number $x$ s.t. $Wx=x$
  86. Enumerable disjoint subsets whose union is equal to the union of the sets
  87. Recursion Theorem : why does $SELF$ need $A$ and $B$ parts?

  88. Constructible enumerable set
  89. Decide whether DFA have useless states

  90. Is the equality of two DFAs a decidable problem?

  91. Example of decidable set whose preimage is not decidable
  92. How strong is an countable infinity large circult?
  93. Are there any countable sets that are not computably enumerable?

  94. Why does the time/space tradeoff exist

  95. Undecidable Problem for Regular Languages
  96. Rice's Theorem for Total Computable Functions
  97. Why is $A \leq_T \bar{A}$?

  98. Language of Turing machines that never visit some given state

  99. NTM's and the halting problem

  100. Show that RE is closed against right-quotient