# 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
1answer
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 ...
1answer
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 ...
0answers
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 ...
0answers
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)$ ...
3answers
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 ...
2answers
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 ...
1answer
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$, ...
1answer
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 : ...
0answers
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 ...
1answer
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 ...
0answers
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 ...
2answers
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 ...
2answers
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 ...
2answers
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 ...
2answers
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 ...
1answer
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 ...
1answer
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 ...
0answers
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 ...
1answer
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: "...
0answers
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 ...
0answers
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 ...
0answers
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 ...
2answers
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, ...
0answers
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.
0answers
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 ...
1answer
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 ...
3answers
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 ...
1answer
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>$...
1answer
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 ...
1answer
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 ...
2answers
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 ...
0answers
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 ...
1answer
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 ...
0answers
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 ...
6answers
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....
1answer
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 &\...
1answer
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 ...
0answers
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.
0answers
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.
1answer
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. ...
1answer
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 ...
1answer
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.
1answer
111 views

0answers
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:...
1answer
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 ...