Questions tagged [turing-machines]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
29 views

Language which is recursively enumerable but not recursive [duplicate]

Can someone provide me with some examples of languages which are recursively enumerable but are not recursive. I know that there exist some languages which are not Recursive but recursively enumerable ...
2
votes
1answer
24 views

Turing Machine equivalence in MinTM proof

The proof with contradiction that $MIN_{\mathrm{TM}}$ is not Turing-recognizable from Michael Sipser's textbook "Introduction to the Theory of Computation" (Theorem 6.7) is as follows: $C=$ "On ...
1
vote
2answers
42 views

L(M)=L where M is a TM that can move right or stay, so L is decidable

Suppose that L(M)=L where M is a one tape TM that can move right or stay. I need to Show that L is decidable. I thought of reducing a PDA to this TM, since moving to the right is equivalent to ...
2
votes
1answer
27 views

Böhm-Jacopini theorem

I had a discussion with a friend developer and teacher. He told me about the Structured program theorem arguing that this theorem is one of the most important to know about. However, I have never ...
0
votes
1answer
23 views

What is the intuition behind the relationship between space and time for an algorithm? [duplicate]

I believe I have heard that you can never have more space than the algorithms running time. I could be wrong, maybe other way around. What is the intuition behind this?
1
vote
1answer
33 views

What is a trivial language?

I have heard the quote "L is a trivial language" What does this mean and how do we relate this to Turing machines and complexity theory?
2
votes
1answer
54 views

Turing Machines proof notations

In context of "Computability", I have went over some proofs for Recursion Theorem using Turing Machine description. A TM $M$ stands for a single tape Turing machine and $\langle M \rangle$ is the ...
0
votes
1answer
69 views

Prove completeness of a language with Turing Machine

I'm trying to prove that a simple computer language is Turing Complete. For that, I did some researches about Turing Machine and I found (if I understand correctly), that we can prove that by simuling ...
0
votes
1answer
123 views

What does it mean for a TM to solve a problem?

When we say a TM solves a problem, what does this mean?
1
vote
1answer
17 views

What is the link between the language defined by the Turing Machine and the algorithm that the Turing machine implements?

What is the link between the language defined by the Turing Machine and the algorithm that the Turing machine implements? I.e. What is the link between the language and the algorithm
0
votes
1answer
13 views

Turing Machines: What is the difference between the language realised by a problem and the language for which the TM accepts on?

A decision problem A corresponds to the language L1 if L1 contains all of the solutions to A. A language L2 is defined as the set of all inputs to which a TM halts and accepts. What is the link ...
1
vote
1answer
20 views

Can a Turing Machine be defined over many languages?

What does it mean, if possible, for a Turing machine to be defined over many languages?
5
votes
2answers
2k views

Turing Machines: What is the difference between recognizing, deciding, total, accepting, rejecting?

I have seen a remark saying "we usually say that a turing machine accepts/rejects a string, while it decides a language" Is this correct? As I have also seen places where we mention a Turing machine "...
2
votes
1answer
42 views

D has polynomial verifyer, the certificate for any word $w \in D$ is at most O(|log w|) space. Prove $D \in P$

Given that a language D has a polynomial verifier, and given that for every word $w \in D$, the length of the certificate $c$ is $O(\log|w|)$ space. How can I prove that $D\in P$ ? My idea was to ...
1
vote
2answers
43 views

Is a language whose Turing Machine doesn't halt for some positive cases but for others does not recursive?

Say language $L$ is recursively enumerable, but not recursive. Say $a$ and $b$ are symbols of the alphabet and $w$ a word. Say we have the following language: $L' = \{ aw | w \in L \} \cup \{ bw | w \...
3
votes
1answer
41 views

How to prove the union of languages recognized by a set of turing-recognizable Turing machines is also turing-recognizable?

Let $G = \{\langle M_1\rangle, \langle M_2\rangle, \langle M_3\rangle,\cdots\}$ be an infinite turing recognizable language, whose members are descriptions of turing machines. How can one prove that ...
1
vote
2answers
47 views

Why is the run time of an $f(n)$ space decider bounded by $2^{O(f(n))}$?

In the proof of Savitch's theorem from the 3rd edition of Sipser's Intro to Theory of Computation, Sipser claims that the maximum time that an $ f(n) $ space nondeterministic Turing machine that halts ...
0
votes
1answer
46 views

Is function `number of TM which terminates on an empty word` computable?

Let f: N → N be a function where ...
0
votes
2answers
31 views

Does there exist an undecidable problem such that the answer is YES for exactly one input to a UTM, and NO for all others?

Suppose I have a universal Turing Machine (UTM) which accepts some input in binary. Is there a computational problem such that the answer to the problem is YES (accepting) for exactly one input (and ...
1
vote
1answer
39 views

Reduction to proof undecidability of the problem: machine M and N accept infinitely many words

I am struggling with the following problem: Decide whether this problem is decidable or not: For two given Turing Machines M and N, there exists infinitely many words accepted by both machine M and ...
2
votes
1answer
62 views

How to prove the language of Turing machines that run at most $4|x|^2$ steps is not recursive?

I am trying to prove that the language $$ L=\{M\mid M\text{ is a TM and for all }x\in \Sigma^*\text{ with }|x|>2, M\text{ on }x\text{ runs at most }4|x|^2\text{ steps}\} $$ belongs to Co-RE but ...
2
votes
1answer
42 views

Does a Non-Deterministic Turing Machine solve all problems in P in constant time?

If a non-deterministic Turing machine can just "guess" the correct answer to a problem, does it do this in constant time/immediately? Also, does this also apply to problems in NP too?
0
votes
2answers
37 views

Are Linear Bounded Automatons Turing Complete?

Linear Bounded Automatons are just Turing Machines with finite tape, instead of infinite tape. But this causes them to not be Turing Complete? Why?
1
vote
1answer
63 views

Is there any relationship between time complexity and space complexity of an algorithm?

For example: If algorithm A takes an input of size n, and has a time complexity of O(a^n) and a space complexity of O(1) Is there a way to increase the space complexity to something like O(n^2) that ...
1
vote
2answers
25 views

Set of steps that cannot be implemented on a Turing machine

Is there an example of a "set of steps" that we thought was an algorithm, but later was shown not to be an algorithm because it could not be implemented on a Turing machine?
0
votes
2answers
49 views

Questions about Turing Machine

Below I will list a concrete example and the confusion it causes. Let's first say we have a decision problem, which is: "Is X <= 400?" We define the alphabet as the set of natural numbers. The ...
0
votes
0answers
27 views

Is Halting problem only applicable to infinite languages

Is the halting problem, only applicable for infinite languages? I assume that if the language is finite, then we can search over all words?
0
votes
0answers
25 views

are all problems solvable given infinite time?

Given a turing machine which has unlimited memory and time, can it solve all problems or are there a class of problems that cannot be solved even with unbounded power. Is there a way to prove this?
0
votes
1answer
19 views

In a Turing machine, what is the difference between the instruction table and the algorithm?

In a Turing machine, what is the difference between the instruction table and the algorithm? The instruction table seems to be an algorithm for completing the task no?
1
vote
1answer
59 views

How to prove $L \notin \texttt{DSPACE}(f)$

I want to prove that a language $L$ is not in $\texttt{DSPACE}(f(n))$, the class of languages that a deterministic Turing machine can decide with fixed tape length of $f(n)$ (wiki). That is, I want to ...
0
votes
1answer
41 views

Turing machine and boolean circuits

As an example of languages that are in P/poly is the UHALT Problem : UHALT = { 1^n: n's binary expansion encodes a pair such that M halts on input x} We can create a boolean circuit of just AND ...
2
votes
1answer
31 views

Can such a Turing-recognizable language exist?

Suppose $\Sigma = \{a,b\}$. Is the following claim correct? There exists a Turing-recognizable language $L \subseteq \Sigma^*$ such as its complement is not Turing-recognizable, and for all $n \in \...
3
votes
1answer
42 views

Uncomputably coded model of computation

There are many different but equivalent models of computation. I assume their equivalence is shown by coding input of one model to the input of the other model and making an argument why should there ...
1
vote
1answer
33 views

Superset of another language and recognizability of turing machines

$L_1$ = $\{\langle M \rangle \mid M$ is a turing machine and $M$ halts on some string$\}$ $L_2$ = $\{\langle M \rangle \mid M$ is a turing machine and $M$ halts on all strings $\}$ a) Is $L_2$ a ...
1
vote
1answer
45 views

Is $ L = \{ a^n\ |\ a^n \not\in L_n \} $ Turing recognizable (recursively enumerable)?

Say $ \Sigma = \{a\} $, $M_1, M_2, ... $ is an enumeration of all TMs that recognize languages over $\Sigma$ and $L_1, L_2, ... $ are respectively the languages that are recognized by those TMs. We ...
1
vote
1answer
69 views

Are all compilers Turing Machines?

So the definition of a compiler I got is that: A compiler takes a string as input and checks if that string is syntactically correct, then outputs "Yes" or "No". So does that mean all compilers ...
1
vote
0answers
15 views

How to adapt proof of the ND time hierarchy theorem for alternate definition of NDTM?

For reference, the version of the nondeterministic time hierarchy theorem in question is this one: The relevant portion of the proof in question (also from Arora-Barak) is here: Arora-Barak define a ...
2
votes
1answer
28 views

One-taped RAM vs Multi-taped RAM

In Turing Machine, we know that there's (fine-grained complexity) difference between one-tape, 2-taped and multi-taped TM, even though they could be simulated efficiently. (Well, actually I'm not ...
4
votes
1answer
259 views

How does a Turing machine with one tape read its input?

It's often implicitly assumed that we don't have to pay much attention to the difference between the program (which specifies the function being computed) and the input (the value on which that ...
0
votes
1answer
35 views

Turing machine loop and reject example

I'm getting confused on these both. Reject the string does a stop while loop the machine goes on and on. My textbook has one example on a reject state and no physical one for loop: Assume that no ...
0
votes
0answers
23 views

Multi-tape to single tape Turing Maching transition complexity

Suppose we have a k-tape Turing machine M and we wanna model it with a Single tape Turing machine N with a register. Suppose the time complexity of M is T(n): ...
2
votes
1answer
32 views

Complexity of a Turing Machine when changing its alphabet to binary

I found in 'Computational Complexity: A Modern approach' Book the following statement that i dont quite understand its proof: For every f : {0, 1}∗ → {0, 1} and time-constructible T : N → N, if f ...
1
vote
1answer
30 views

Recognizably turing machine question (reject / loop)

The definition of proving recognizability using dove tailing is below. However I'm wondering if we can also prove loop or reject in the same way? Give a deterministic TM D that recognizes L such that ...
2
votes
1answer
54 views

Non-Deterministic Turing machine vs Probabilistic Turing Machine vs Deterministic Turing Machine

What is the difference between a Non-Deterministic Turing machine, Probabilistic Turing Machine and a Deterministic Turing Machine ?
3
votes
1answer
29 views

Why do we simulate the universal TM to simulate another TM M instead of simulating M directly?

In the proof of the time hierarchy theorem given on page 69 of Arora-Barak, we define a TM D as follows: "On input $x$, run for $|x|^{1.4}$ steps the Universal TM $\ \mathcal{U}$ of Theorem 1.9 to ...
0
votes
1answer
49 views

Advantages of Lambda calculus over Turing machine and vice versa [closed]

What kind of advantages does Lambda calculus have over Turing machine, and vice versa?
1
vote
0answers
17 views

What's the difference between Acfg and ALLcfg

In computational theory, and talking about CFGs, Turing Machines, and so forth I haven't a satisfactory explanation or definition for what ATM means versus ALLTM or the same or similar uses with ...
2
votes
1answer
85 views

Can these two languages be reduced to one another?

Given: $L_1=\left\{ \left\langle M\right\rangle :L\left(M\right)\ni w_{0}\right\}$ $L_2=\left\{ \left\langle M\right\rangle :L\left(M\right)=\left\{ w_{0}\right\} \right\}$ I believe I've managed ...
2
votes
1answer
36 views

Prove/Disprove: Every two non-trivial NP-complete problems are decreasing reducible?

We say that two languages $L_1,L_2$ are decreasing reducible if there exists a polynomial time reduction $f:\Sigma^*\to\Sigma^* $ and there exists $n\in\mathbb{N}$ such that for every $x\in\Sigma^*$ ...
1
vote
1answer
35 views

Dove tailing questions about accepting language

$L = \{M | \text { M is a TM and there exist some string w that contains five 1's such that M halts}\}$ Where $\Sigma =\{0,1\}$ let $w_1, w_2, \cdots, \in \Sigma^*$ be an effective enumeration. We ...