# Questions tagged [turing-machines]

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

1,569 questions
Filter by
Sorted by
Tagged with
123 views

### Language of TM is Undecidable

why is this Problem$$L = \{ \langle M\rangle \mid L(M) \text{ is undecidable}\}$$ undecidable? I thought if we know $L(M)$ the turingmaschine accepts all $x \in L(M)$, so $L(M)$ is in every case ...
41 views

### Is there a relation between the size of the domain/range of a function and its computability?

This was a question given in a course, without answer. The referenced literature (just a few books) do not cover it, unfortunately. I think there is no relation with the range as the range of the ...
63 views

### Correctness proof: induction on sequence of steps, need a stronger claim?

Im trying to prove the correctness of the construction proposed in this site answer: a two stack PDA that simulates a Turing Machine. By "correctness" i mean to prove more or less formally that we can ...
61 views

### How can an arbitrary Turing machine running for $t$ steps be simulated in $O(n \log(n))$ steps?

I'm confused about a point regarding the Time Hierarchy Theorem. In order to establish the upper bound for this theorem it's necessary to show the following: We're given $(\langle M \rangle, t)$ ...
104 views

### Does undecidability violate Turing completeness? Shouldn't “complete” include “decidability”? [closed]

Does undecidability violate Turing completeness? Shouldn't "complete" include "decidability"? That is, if one has a language that's Turing complete, but expresses infinite computation (i.e. may not ...
106 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 ...
69 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$, ...
201 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 : ...
109 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 ...
53 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 ...
122 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 ...
53 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 ...
54 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 ...
402 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 ...
25 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 ...
79 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 ...
33 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 ...
124 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: "...
51 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 ...
49 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 ...
134 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, ...
20 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.
26 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 ...
71 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>$...
362 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 ...
108 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 ...
140 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 ...
42 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 ...
38 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 ...
26 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....
21 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 &\...
51 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 ...
22 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.
16 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.
119 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. ...
240 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 ...
41 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.
111 views

47 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:...
69 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 ...