turing-machines

  1. Can the turing machine accept these type of languages in O(n)? or better? $L = \{a^n b^n c^n ... d^n | n > 0\}$
  2. Is the set of all Context free languages a Context sensitive Language? ( can we build a LBA that decides whether a given language is CFL or not?)
  3. Decidability of the TM's computing a non-empty subset of total functions

  4. Can a Turing machine determine if a set is accepted by a another Turing machine?

  5. The set of turing machine that stops with input zero is not recursive

  6. TM to detect repeats of any other TM and input value
  7. Determine if a language is decidable

  8. Automata - PDA and TM {a^3n b^2n:n=0,1,2,…}
  9. Turing machine - Calculate the word in base 10
  10. Is the Rice's theorem applicable to $\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$?

  11. Non recursively enumerable language proof by reduction to non-HP

  12. Adding the requirement of linear time on infinitely many inputs into the class $P$

  13. Proving a language is not Turing-recognizable by reduction from $D = \{\langle M\rangle \mid M \text{ rejects input }\langle M\rangle\}$

  14. Show that the single-tape TMs that can not write on the portion the portion of the tape containing the input string recognize only regular languages

  15. A second question on "Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs"
  16. How to reduce halting problem to the problem of whether a Turing Machine accepts infinitely many inputs?

  17. Does godel's incompleteness theorem still hold if we have a TM that can do an infinity amount of computations?

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

  19. Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs

  20. How to prove that a language of turing machines with different language sizes is undecidable?

  21. Which is the best approach to solve Turing machines exercises?

  22. How to compute the language {ww | w ∈ {0,1}*} within a Multitape Turing Machine?
  23. Show that the collection of Turing-recognizable languages is closed under homomorphism

  24. Question about proving that Rado's function is non-computable

  25. L = {<M> | M is a TM and halts on every input after 5 steps exactly } - is L decidable?

  26. Can there be a perfect chess algorithm?
  27. Turing Machine that halts iff the tape contains at least two '1's

  28. is L = {<M> | M is a tm such that t(n) = O(n^2) } in R? RE? CO-RE? CO-RE / RE?
  29. Turing machine that accepts L = {#a != #b}
  30. Writing a Turing Machine that convers a number from binary to decimal

  31. Standard notation for the language of the universal Turing machine?

  32. If A is mapping reducible to B and A is recognizable, then is B recognizable too?

  33. NP Problems are exponential

  34. Turing machine - Check if $a^p$ is prime

  35. How does this reduction to prove undecidability account for epsilon?

  36. Solve every problem with recursion

  37. Simulating QC using nondeterministic Turing machine

  38. Can a Turing machine decide the language $L_\emptyset$ of machines with empty language?

  39. Is emptiness of the intersection of the languages of two TMs decidable?

  40. How come $REC$ languages are included in $NRE$

  41. Implementing Deterministic Turing Machine

  42. Finite State Machine trasition possibilities

  43. Detect whether one Turing machine invokes another

  44. Prove by reduction EVEN TM is undecidable
  45. L = { <M>, M is a DFA accepting all strings except finitely many

  46. Does every turing machine have an equivalent, single-state, n-tape turing machine?
  47. How to show that any computable function is bounded above by Busy Beaver Function?

  48. Does a turing machine halt with input left on tape?
  49. developing a Turing Machine that checks for powers of 2

  50. Concatenation of two Turing machines

  51. Why is "accepted by Turing Machine with even number of states" a trivial property?
  52. How Turing recognizer recognizes any string?

  53. Turing Machines and Algorithm for Language Acceptance

  54. What is the complexity of the following problem?

  55. It is possible to write any program (i.e. Turing complete) with just one single expression?
  56. Set of infinite DFA's
  57. Turing machine halting in at least 100 steps on all inputs
  58. Why is set of Turing machine set DD = {⟨M⟩ | ⟨M⟩⟨M⟩ not in L(M)} not decidable?

  59. How can (generalized) Turing Machine tapes be defined?

  60. If set $C$ is recursively enumerable and $B$ is Recursive, and if $B-C$ is recursively enumerable then is $C$ recursive or not?
  61. A question about $O(T \log T)$ simulation of a TM on some input by universal turing machine

  62. Doubt on dovetailing

  63. Relating accepting/rejecting paths to satisfying/falsifying assignments in (Cook, 1971)

  64. If all computations of non deterministic Turing machine on the input string are all accept then is the boolean formula of them a tautology?
  65. P=NP, isn't it?
  66. Definition of NP

  67. Is the boolean formula generated from the Cook's reduction necessarily in conjunctive normal form?

  68. Is there a complexity metric for finite state machines?

  69. Whether TM accepts epsilon?

  70. Does polynomial time reduction from CNFFAL to CNFSAT is also polynomial time reduction from CNFSAT to CNFFAL?

  71. Give an example of a language where both L and ¬L is not semidecidable?

  72. turing machine for the language L ={w#w' where w<w'}

  73. NP and verifiability equivalence - does this guarantee that any certificate can be verified in polynomial time?
  74. Is a computer equivalent to a Turing machine or linear bounded automata?

  75. Why does a Turing Machine need at least two states?
  76. P reduction between np-complete to np-complete

  77. complement of a NON RECURSIVELY ENUMERABLE LANGUAGE

  78. Difficulty in reducing non halting problem to a given problem

  79. Assuming that $P \neq NP$, show that there exist sets $A$ and $B$ in $NP$ such that neither $A \leq _T^p B$ nor $B \leq _T^p A$
  80. R.E or non R.E?
  81. What does "effective enumeration" in Turing machines mean?

  82. What is the difference between RAM and TM?

  83. How would one reduce HaltTM to ATM
  84. Classification of the complement of a language
  85. Why RAM model is prefered over Turing Model while studying algorithm?
  86. Why models of computation are primarily focused on machines?
  87. How to calculate the complexity of a TM?

  88. Proving that a class of languages is a subset of RE for Rice Theorem

  89. prove that the language LRE is decidable
  90. Proof that if a function is computable with standard programs it is computable with Turing Machines
  91. Can Atm language be reduced?

  92. Is it possible to prove Turing irreducibility

  93. Reduction from L to Htm

  94. Has this generalization of Turing machines studied before?

  95. What are applications of the levels of the Chomsky hierarchy?

  96. Reduction function from A to its complement

  97. Is a Turing machine without the ability to write on blank cells less powerful than standard Turing?
  98. Turing Machine vs Universal Turing Machine

  99. Is the the complement of the Halting problem NP-hard
  100. Is the set of TMs whose language reduces to a fixed CFL also CFL?