<we><edit> <!-- questions and answers -->
turing-machines
context-free
memory-management
search-trees
pumping-lemma
programming-languages
neural-networks
formal-languages
np-hard
correctness-proof
proof-techniques
halting-problem
compilers
time-complexity
image-processing
automata
arithmetic
closure-properties
information-theory
network-flow
dynamic-programming
np
quantum-computing
computation-models
space-complexity
turing-machines
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\}$
formal-languages
turing-machines
automata
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?)
formal-languages
turing-machines
automata
context-free
Decidability of the TM's computing a non-empty subset of total functions
computability
turing-machines
reductions
undecidability
Can a Turing machine determine if a set is accepted by a another Turing machine?
computability
turing-machines
sets
The set of turing machine that stops with input zero is not recursive
computability
turing-machines
termination
TM to detect repeats of any other TM and input value
computability
turing-machines
Determine if a language is decidable
computability
turing-machines
Automata - PDA and TM {a^3n b^2n:n=0,1,2,…}
turing-machines
automata
pushdown-automata
Turing machine - Calculate the word in base 10
turing-machines
base-conversion
Is the Rice's theorem applicable to $\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$?
turing-machines
computability
undecidability
rice-theorem
Non recursively enumerable language proof by reduction to non-HP
turing-machines
reductions
halting-problem
Adding the requirement of linear time on infinitely many inputs into the class $P$
complexity-theory
turing-machines
computability
time-complexity
polynomial-time
Proving a language is not Turing-recognizable by reduction from $D = \{\langle M\rangle \mid M \text{ rejects input }\langle M\rangle\}$
computability
turing-machines
reductions
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
complexity-theory
turing-machines
computability
A second question on "Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs"
formal-languages
turing-machines
computability
undecidability
How to reduce halting problem to the problem of whether a Turing Machine accepts infinitely many inputs?
turing-machines
reductions
undecidability
halting-problem
Does godel's incompleteness theorem still hold if we have a TM that can do an infinity amount of computations?
turing-machines
incompleteness
Simulating Turing Machine with writing only on non-input fields on read-only Turing machine
complexity-theory
computability
turing-machines
Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs
turing-machines
computability
decision-problem
How to prove that a language of turing machines with different language sizes is undecidable?
turing-machines
undecidability
Which is the best approach to solve Turing machines exercises?
turing-machines
How to compute the language {ww | w ∈ {0,1}*} within a Multitape Turing Machine?
turing-machines
Show that the collection of Turing-recognizable languages is closed under homomorphism
formal-languages
turing-machines
closure-properties
Question about proving that Rado's function is non-computable
turing-machines
computability
check-my-answer
L = {<M> | M is a TM and halts on every input after 5 steps exactly } - is L decidable?
turing-machines
Can there be a perfect chess algorithm?
algorithms
turing-machines
Turing Machine that halts iff the tape contains at least two '1's
turing-machines
is L = {<M> | M is a tm such that t(n) = O(n^2) } in R? RE? CO-RE? CO-RE / RE?
turing-machines
computability
Turing machine that accepts L = {#a != #b}
formal-languages
turing-machines
automata
Writing a Turing Machine that convers a number from binary to decimal
turing-machines
base-conversion
Standard notation for the language of the universal Turing machine?
computability
terminology
turing-machines
If A is mapping reducible to B and A is recognizable, then is B recognizable too?
turing-machines
reductions
NP Problems are exponential
complexity-theory
turing-machines
Turing machine - Check if $a^p$ is prime
turing-machines
computability
How does this reduction to prove undecidability account for epsilon?
turing-machines
reductions
decision-problem
mapreduce
Solve every problem with recursion
turing-machines
computability
computation-models
recursion
Simulating QC using nondeterministic Turing machine
turing-machines
computation-models
nondeterminism
quantum-computing
simulation
Can a Turing machine decide the language $L_\emptyset$ of machines with empty language?
turing-machines
computability
undecidability
Is emptiness of the intersection of the languages of two TMs decidable?
computability
turing-machines
undecidability
How come $REC$ languages are included in $NRE$
turing-machines
Implementing Deterministic Turing Machine
complexity-theory
turing-machines
Finite State Machine trasition possibilities
complexity-theory
turing-machines
finite-automata
Detect whether one Turing machine invokes another
turing-machines
computability
Prove by reduction EVEN TM is undecidable
turing-machines
computability
undecidability
L = { <M>, M is a DFA accepting all strings except finitely many
turing-machines
undecidability
Does every turing machine have an equivalent, single-state, n-tape turing machine?
turing-machines
computation-models
simulation
How to show that any computable function is bounded above by Busy Beaver Function?
computability
turing-machines
Does a turing machine halt with input left on tape?
turing-machines
developing a Turing Machine that checks for powers of 2
algorithms
turing-machines
primes
Concatenation of two Turing machines
turing-machines
Why is "accepted by Turing Machine with even number of states" a trivial property?
turing-machines
computability
rice-theorem
How Turing recognizer recognizes any string?
turing-machines
undecidability
Turing Machines and Algorithm for Language Acceptance
computability
turing-machines
What is the complexity of the following problem?
complexity-theory
turing-machines
reductions
satisfiability
decision-problem
It is possible to write any program (i.e. Turing complete) with just one single expression?
formal-languages
turing-machines
automata
lambda-calculus
church-turing-thesis
Set of infinite DFA's
formal-languages
turing-machines
regular-languages
Turing machine halting in at least 100 steps on all inputs
formal-languages
turing-machines
Why is set of Turing machine set DD = {⟨M⟩ | ⟨M⟩⟨M⟩ not in L(M)} not decidable?
turing-machines
computability
undecidability
How can (generalized) Turing Machine tapes be defined?
turing-machines
If set $C$ is recursively enumerable and $B$ is Recursive, and if $B-C$ is recursively enumerable then is $C$ recursive or not?
turing-machines
computability
undecidability
recursion
A question about $O(T \log T)$ simulation of a TM on some input by universal turing machine
complexity-theory
turing-machines
time-complexity
Doubt on dovetailing
turing-machines
proof-techniques
computation-models
Relating accepting/rejecting paths to satisfying/falsifying assignments in (Cook, 1971)
complexity-theory
turing-machines
satisfiability
strings
nondeterminism
If all computations of non deterministic Turing machine on the input string are all accept then is the boolean formula of them a tautology?
complexity-theory
turing-machines
satisfiability
strings
nondeterminism
P=NP, isn't it?
complexity-theory
turing-machines
reductions
satisfiability
p-vs-np
Definition of NP
turing-machines
np
decision-problem
Is the boolean formula generated from the Cook's reduction necessarily in conjunctive normal form?
complexity-theory
turing-machines
satisfiability
nondeterminism
polynomial-time
Is there a complexity metric for finite state machines?
turing-machines
finite-automata
Whether TM accepts epsilon?
turing-machines
computability
Does polynomial time reduction from CNFFAL to CNFSAT is also polynomial time reduction from CNFSAT to CNFFAL?
complexity-theory
turing-machines
reductions
satisfiability
nondeterminism
Give an example of a language where both L and ¬L is not semidecidable?
turing-machines
computability
undecidability
closure-properties
semi-decidability
turing machine for the language L ={w#w' where w<w'}
formal-languages
turing-machines
NP and verifiability equivalence - does this guarantee that any certificate can be verified in polynomial time?
turing-machines
np
nondeterminism
Is a computer equivalent to a Turing machine or linear bounded automata?
turing-machines
Why does a Turing Machine need at least two states?
formal-languages
turing-machines
P reduction between np-complete to np-complete
complexity-theory
formal-languages
turing-machines
reductions
complement of a NON RECURSIVELY ENUMERABLE LANGUAGE
turing-machines
computability
undecidability
Difficulty in reducing non halting problem to a given problem
turing-machines
computability
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$
complexity-theory
turing-machines
R.E or non R.E?
turing-machines
computability
What does "effective enumeration" in Turing machines mean?
turing-machines
computability
terminology
What is the difference between RAM and TM?
turing-machines
computation-models
How would one reduce HaltTM to ATM
turing-machines
computability
reductions
Classification of the complement of a language
turing-machines
computability
Why RAM model is prefered over Turing Model while studying algorithm?
algorithms
turing-machines
Why models of computation are primarily focused on machines?
turing-machines
lambda-calculus
computation-models
How to calculate the complexity of a TM?
complexity-theory
turing-machines
Proving that a class of languages is a subset of RE for Rice Theorem
turing-machines
computability
rice-theorem
prove that the language LRE is decidable
turing-machines
computability
reductions
Proof that if a function is computable with standard programs it is computable with Turing Machines
turing-machines
proof-techniques
Can Atm language be reduced?
complexity-theory
turing-machines
reductions
Is it possible to prove Turing irreducibility
complexity-theory
turing-machines
computability
reductions
Reduction from L to Htm
complexity-theory
formal-languages
turing-machines
reductions
Has this generalization of Turing machines studied before?
turing-machines
reference-request
What are applications of the levels of the Chomsky hierarchy?
formal-languages
turing-machines
Reduction function from A to its complement
complexity-theory
formal-languages
turing-machines
reductions
Is a Turing machine without the ability to write on blank cells less powerful than standard Turing?
formal-languages
turing-machines
computability
automata
Turing Machine vs Universal Turing Machine
turing-machines
Is the the complement of the Halting problem NP-hard
turing-machines
reductions
np-hard
Is the set of TMs whose language reduces to a fixed CFL also CFL?
formal-languages
turing-machines