Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
-3
votes
3answers
62 views
Does undecidability violate Turing completeness?
Does undecidability violate Turing completeness?
That is, if one has a language that's Turing complete, but expresses infinite computation, then why is it meaningful for it to be called "Turing ...
1
vote
1answer
31 views
Are $A$ and $B$ necessarily be decidable if $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable and $A$ & $B$ being exhaustive?
I found the following question
Suppose A and B are recursively enumerable languages such that $A∪B=Σ∗$. Further, suppose $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable. Which of the following is ...
1
vote
1answer
33 views
Space and time complexity of $L = \{a^nb^{n^2} \mid n≥1\}$
Consider the following language:
$$L = \{a^nb^{n^2} \mid n≥1\}\,$$
When it comes to determining time and space complexity of a multi-tape TM, we can use two memory tapes, the first one to count $n$, ...
2
votes
1answer
45 views
Confusion about proof of undecidability of REGULAR TM in Sipser's book
in the book "Introduction to the Theory of Computation" by Michael Sipser there is an example of undecidable languages in which there is a language REGULR_TM which is described as follows :
...
2
votes
0answers
58 views
Equivalence between different Turing Machines and a definition of simulation
Im having some difficulty understanding how the following two concepts could be related.
Equivalence between TMs as is commonly tought
According to this site answer, to prove a standard TM model to ...
1
vote
1answer
44 views
RAM BSS model based (or its variant) computer recognizing Boolean languages
Can any RAM BSS model based machine, or machines which are variants, recognize boolean languages(languages such as P, NP, or the like)? If so which languages are recognizable by RAM/BSS nachines, or ...
2
votes
0answers
27 views
Is the language $L$ of coded CFG's Turing decidable?
Consider the following language
$L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$}
Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
1
vote
2answers
45 views
Recognizer for decidable language and words it doesn't halt on
Suppose we have a decidable language B (there exists some TM that decides it). Suppose we have another TM M which only ...
1
vote
2answers
47 views
Is there a name for this type of Turing machine?
I'm considering turing machines with tape alphabet equal to $\{0,1\}$ and the blank symbol equal to $0$. Is there a name for this type of Turing machines? Isn't this type the one computers are based ...
0
votes
1answer
20 views
Give a Context Free Language, is the complement of this language always recursive(REC)?
I have seen some people make an argument that given the fact that Context Free Languages are proper subset of REC which is closed under complementation thus complement of a CFL must be in REC. I ...
2
votes
2answers
374 views
Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?
I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this ...
1
vote
1answer
19 views
Set Difference of Two RE Languages - An Intuitive Idea of Why It's Not Closed
I'm new to studying formal languages, so apologies if I get a lot of basic stuff wrong, but I'm trying to get an intuitive understanding of why the difference between two Recursively Enumerable ...
1
vote
1answer
30 views
How do I construct a NTM that accepts the language consisting of the coding of turing machines that halt on one input?
I currently have a problem with the following question:
Let $L = \{ \langle M \rangle \mid \exists w: \text{$M$ halts for $w$ in at most $|w|^3$ steps} \}$.
Construct an NTM (non-deterministic Turing ...
0
votes
0answers
18 views
What is abstract machine for parallel multiple context free grammar (PMCFG)?
It is said, that PMCFG (Parallel multiple context free grammar) http://www.aclweb.org/anthology/P93-1018 is mildly context-sensitive grammar. My question is - what abstract machine can be used for ...
1
vote
1answer
31 views
How to prove that a problem is undecidable by using the Halting problem?
I cannot understand how to reduce the halting problem to a property to show that is undecidable.
For example, I have this property of a Turing Machine and I have to prove if it's recursive or not:
"...
1
vote
0answers
26 views
RO turing machine with finite memory
Consider the following:
A weak TM is a TM with finite tape in size $k$ which can only read its input values. note: the tape size does not include the input length.
I need to determine whether if the ...
0
votes
0answers
16 views
Recursively Enumerable and Recursive
Consider below two languages
$L_1=\{<M>|$ M is a turing machine, $M_0$ is a TM that halts on all inputs, and $M_0 \in L(M) \}$
$L_2=\{<M>|$M is a TM, $M_0$ is a TM that halts on all ...
1
vote
0answers
26 views
Why full Chomsky hierarchy is so detailed, if there are decidable recursive languages?
One can have a look on the Chomsky hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy , especially the inset named "Automata theory: formal languages and formal grammars" at the bottom of the ...
1
vote
2answers
99 views
If a non-deterministic Turing machine runs in f(n) space, then why does it run in 2^O(f(n)) time?
Assuming that f(n) >= n.
If possible, I'd like a proof in terms of Turing machines. I understand the reason why with machines that run on binary, because each "tape cell" is a bit with either 0 or 1, ...
0
votes
0answers
15 views
How to prove that models of indirect and direct RAM machines are equivalent?
as in the title, I am looking for a formal proof how to show that models of indirect and direct RAM (random-access) machines are equivalent. I would really appreciate your help.
0
votes
0answers
10 views
create two- or three-tape Turing machine to recognize the language $0^{2^n}$
I am creating a two-tape Turing machine to recognize the language $\{0^{2^n}|n\geq 0\}$. My idea is to put an input string, such as 0000, at the first tape, and use the second one to count the number ...
0
votes
1answer
22 views
Show that $A_\mathrm{LBA}$ is PSPACE-Complete?
I want to show that $A_\mathrm{LBA}$ is PSPACE-Compelte.
Say we proved it is in PSPACE. Now for PSPACE-HARD:
I had an idea, which was very similar to some solution i found on the web- say we have a ...
1
vote
3answers
60 views
Proof Idea: There are irrational numbers whose decimal expansion cannot be computed
The online lecture I am watching stated a proof idea:
The set of all possible programs is countably infinite, yet
the set of irrational numbers is uncountably infinite.
I don't think this is ...
0
votes
1answer
24 views
Which of the following is recursive
Consider below two Languages
$L1=\{<M>|$M takes atleast 2000 steps on some input $\}$
$L2=\{<M>|$M takes atleast 2000 steps on all inputs$\}$
Where for each Turing machine M, $<M>$...
6
votes
1answer
327 views
Whats the difference between an oracle and a decider in Computational Theory?
I'm learning about Turing reductions at the moment and I'm just wondering is there any difference between an oracle and a decider, As they seemingly do the exact same thing. I understand the point of ...
0
votes
1answer
22 views
Binary search in log time on a Turing Machine
I was thinking about TM (Turing Machine) as a computation model, and I came up with the following question :
Is it possible to make a TM that answers binary search (tell wether $x$ belong to a sorted ...
1
vote
2answers
86 views
Why are not all recursive languages undecidable?
I learned that recursive language are decidable; correct me if I am wrong. However, I have found some arguments that seem to contradict this. These may or may not be correct; please let me know.
If ...
1
vote
0answers
30 views
This Universal Turing Machine
I was reading this answer about Turing machines and it refers to a bussiness-card-sized one, which claims to be a universal Turing machine, based on this paper. However, I don't understand the logic ...
1
vote
1answer
21 views
Verifier for A_tm in polynomial time - how to formally prove it does not exist?
How would you formally prove the non-existance of a polynomial time verifier for $A_\mathrm{TM}$?
I mean we can't just say that in order to read a certain certificate we need more than poly-time ...
0
votes
0answers
11 views
How to know if a lanugae is undecidable or semi-decidable
I recently learnt about undecidable languages and semi-decidable languages. But I am still quite confused on how I can determine if a language is semi-decidable. Is there any standard theorem or axiom ...
6
votes
6answers
5k views
The first Turing machine
Does anyone know how efficient was the first Turing machine that Alan Turing made? I mean how many moves did it do per second or so... I'm just curious. Also couldn't find any info about it on the web....
0
votes
1answer
18 views
Given set of grammar rules, how to find if they correspond to Context-free or unrestricted
Given set of grammar rules, how to find if they correspond to Context-free or unrestricted?
Just for Understanding (don't solve the below one),
eg:
\begin{align}
S &\rightarrow B/A, \\
1B &\...
1
vote
1answer
26 views
Two Turing machines $M_1$ and $M_2$ with $L(M_1) \subseteq L(M_2)$
Suppose $M_1$ and $M_2$ are two Turing machines such that $L(M_1)\subseteq L(M_2)$. Which of the following is true?
(A) On every input on which $M_1$ does not halt, M2 does not halt
(B) On every ...
0
votes
0answers
17 views
Is the set $\{<M> | L(M) \text{is a finite set}\}$ RE, co-RE or neither? [duplicate]
$<M>$ is the encoding of a TM and L(M) is the language accepted.
0
votes
0answers
14 views
Is ${M :|L(M)| \leq 330}$ Recursively enumerable? [duplicate]
M is a Turing machine description, L(M) is the language recognized by M and |L(M)| is the size of this language.
2
votes
1answer
81 views
Which one of these two sets is computably enumerable?
M is a turing machine description, L(M) is recognized by M, |L(M)| is the size of this language.
{M : |L(M)| <= 330}
{M : |L(M)| >= 330}
I don't quite understand what this question is asking. ...
0
votes
1answer
26 views
Lambda Calculus - Call-by-name AND call-by-value reduction
I have been tasked with reducing the following lambda expression:
(λpq.pqp)(λab.a)(λab.b)
using call-by-name and call-by-value reduction strategies.
Call-by-name
strategy: Left-most, outermost ...
1
vote
1answer
35 views
Is the set of context free grammars that generate all words in co-RE?
Is $\{\langle G \rangle | L(G) = \sum^{\star}\}$ in co-RE? $\langle G \rangle$ is the encoding of a context free grammar. My intuition is that this is false.
1
vote
1answer
34 views
Reduce ATM to REGULAR_TM
Consider $\mathsf{REGULAR_{TM}} = \{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language}\}$.
Let $S$ be the following algorithm, which solves $\mathsf{A_{TM}}$: “On input $\...
1
vote
1answer
26 views
Number of divisors of a number - in NP?
I'm trying to show that the language {(m,n)|m has exactly n divisors} is in NP.
The input (m,n) is in binary.
The non-deterministic Turing machine for the language would be:
1) Guess the prime ...
1
vote
0answers
12 views
What is the difference between the input set of a BSS RAM and a language?
I'm currently learning some things about BSS RAMs.
For sake of simplicity, please imagine them as a Turing machine over the reals.
Now, this machine gets some real numbers as input. The input values ...
2
votes
2answers
34 views
Quotient in LOOP program [closed]
I want to construct a LOOP-computable program for the integer division (quotient):
x = a DIV b
The LOOP specification can be seen here: https://en.wikipedia.org/wiki/LOOP_(programming_language)
I ...
0
votes
2answers
40 views
Halting problem of TM which recognize recursive languages is undecidable?
I am preparing for an exam and I came across this question in one of the tests.
Halting problem of Turing machines which recognize recursive languages
is undecidable. (True / False)
The solution ...
0
votes
1answer
37 views
Is this language recognizable?
Let $L = \{M: M\text{ halts on only one of 1100 or 0011 or 0011 or 1000}\}$. I'm trying to determine whether $L$ is decidable.
I don't think it's even recognizable, but I'm not sure. Regardless, I ...
0
votes
0answers
31 views
Turing machine, tape without blanks, does it halt or no?
So I'm lost on this one. We're given a turing machine and an initial tape. Tape is infinitely long in both ways, but all the blanks are taken out. The head is the leftmost nonblank. So the question is:...
0
votes
1answer
37 views
What changes need to be made to a Turing machine to make them equivalent to a PDA, a DFA?
I believe in order to make a Turing machine have the same power as a DFA (by power I mean all languages which a DFA can decided so can the Turing machine) we just don't allow any use of backtracking ...
2
votes
1answer
37 views
Turing machine with semi infinite tape - Prove by construction
I'm studying constrained Turing Machines.
There's a theorem that proves that both infinite and semi-infinite tape TM have the same computational power. The theorem that proves this by emulating a TM1 ...
0
votes
1answer
22 views
Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem.
...Knowing whether a Turing machine will ever output your name on the tape. The language is the set of all TMs that print your name. Reduce from HALT TM.
I had this problem on my exam. From my ...
0
votes
0answers
17 views
Whether language of all turing machines is decidable or undecidable or semi-decidable?
I recently came across this language:
$L=\{<TM>| \text{TM accepts recursively enumerable languages}\}$
It was asked in the question to find out whether language L is decidable or undecidable.
...
0
votes
0answers
26 views
What is the power of a Turing-machine that cannot write?
What is the power of a Turing-machine that cannot write?
So it can still read and go back and forth on the tape, but it cannot write.
I am wondering what this would be equivalent to in the ...
