Questions tagged [turing-machines]

Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.

1,515 questions
156 views

Confusion about proof of undecidability of REGULAR TM in Sipser's book [duplicate]

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 : ...
95 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 ...
52 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 ...
37 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 ...
102 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 ...
51 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 ...
53 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 ...
397 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 ...
24 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 ...
73 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 ...
30 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 ...
106 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: "...
48 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 ...
36 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 ...
47 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 ...
121 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, ...
18 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.
22 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 ...
64 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 ...
70 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 ...
26 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>$...
357 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 ...
91 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 ...
125 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 ...
40 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 ...
37 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 ...
22 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 ...
6k 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....
20 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 &\...
47 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 ...
21 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.
15 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.
116 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. ...
191 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 ...
39 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.
94 views

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 $\... 1answer 49 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 ... 0answers 19 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 ... 2answers 46 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 ... 2answers 52 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 ... 1answer 59 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 ... 0answers 42 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:... 1answer 62 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 ... 1answer 150 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 ... 1answer 42 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 ... 1answer 55 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. ... 0answers 33 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 ... 1answer 53 views Unrestricted grammar which generates$\{ a^1\#a^2\#a^3\#\dots \#a^k \mid k >0 \}$I am looking for an unrestricted grammar which generates the following language:$\{ a^1\#a^2\#a^3\# \dots \#a^k \mid k >0 \}$That is, words like$a\#aa\#aaa\#aaaa\# \dots \# \text{$k$ times '$a$...
I have been having a hard time understanding whether the set $S = \{ M \mid |L(M)| = 5 \}$ is semidecidable or not, where $M$ is a generic Turing Machine and $L(M)$ the language accepted by such TM, ...
Today I did a test in my class, the trace was: Prove that the language $L =\{\langle M\rangle\mid \forall w \in \{0,1\}^\ast: M \text{ accepts }w\implies M \text { accepts }ww \}$, is undecidable ...