We’re rewarding the question askers & reputations are being recalculated! Read more.

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
0answers
22 views

Is the language of turing machines, which return epsilon on its own encoding, decidable?

Is the language $\{ \langle M\rangle | f(\langle M\rangle)=\epsilon\}$ decidable? $f()$ means, that the turing machine returns $\epsilon$ on its own encoding and $\langle M\rangle$ stands for the ...
1
vote
1answer
32 views

Can current quantum computers decide languages that Turing Machines cannot?

I am currently learning Computing Theory at university, and we were on the topic of Turing-Decidability, Recognizability, etc. Showing that a problem is undecidable with Turing machines due to ...
0
votes
0answers
15 views

Possible number of DFAs, NFAs, DPDAs, NPDAs, NDTMs and DTMs for various input parameters

I came across problem asking for possilble number of DFAs for a given number of states and alphabet. I started guessing if we can find possible number different automatas for given number of states, ...
0
votes
1answer
32 views

Turing recognizable but not Turing decidable language cannot have TM do not halt on infinitely many inputs

Sorry, I think I misunderstand the question, It should read as if $L$ is turing-recognizable but not decidable, then there exists infinitely many input that any TM will not halt on it...
0
votes
1answer
40 views

Maximum number of configurations of Turing machine after $n$ moves

I came across following question: What are maximum number of configuration of Turing Machine after $n$ moves? The answer given was: $k^n$, where $k$ is a branching factor. And that "branching ...
0
votes
1answer
15 views

Oblivious Machines and Input Dependency

So I know the Oblivious Turing Machines head position depends on the size of the input word and a number of steps. Can it be modified in such a way that it's not dependent on the size of the input ...
0
votes
0answers
22 views

Semidecidable Turing Machine for L={a,b}*

I have a language L={a,b}* over the alphabet {a,b}. How do I build a Turing Machine that semidecides but does not decide this language? Me and my classmates tried using the macro language to solve ...
0
votes
0answers
30 views

Solution to prove that every recursively enumerable language is accepted by a Turing machine with a single accepting state

In order to prove that every "recursively enumerable language" is accepted by a Turing machine with a single accepting state, my idea is using the following theorem. Theorem: Every nondeterministic ...
2
votes
1answer
30 views

Why can’t you simulate a Turing machine with a one-stack PDA by messing with the stack?

I have heard that a matrix can be modeled as just an one array by declaring increasingly large spaces to be from the second array, and that the least you need for a Turing machine is just a PDA with ...
1
vote
1answer
16 views

Turing machine with k-tape, tape of output

Consider a Turing machine with input alphabet $\{a,b\}$ that computes the following function: $$ f(w, v) = \begin{cases} w & \text{if } \operatorname{length}(w) > \operatorname{length}(v), \\ ...
0
votes
1answer
31 views

Undecidable: $w$ on which a TM M $M$ halts after $\leq w$ steps

The detailed question is: Is there a word $w$ on which a TM M $M$ halts after a maximum of $|w|$ (word length) steps? I highly assume, that this problem is not decidable because in the worst case ...
-1
votes
1answer
35 views

Undecidability of TMs recognizing a decidable language

The language $L = \{ \text{M} \mid \text{M is a TM and the set of words w such that M halts on w is decidable} \}$ is given. I need to prove that $L$ is NOT Turing recognizable. I've got a hint: it ...
0
votes
0answers
23 views

How to proof a function is not computale [duplicate]

I wish to undestand how to proof a function is/is not computable. I found this example online (without solution) beacuse I was thinking was easy to understand, but I am stuck in understanding how to ...
-1
votes
0answers
33 views
0
votes
1answer
21 views

On the computable function of a problem that halts

Let's say program $P$ with given input $i$ is found to halt (or doesn’t halt) by a Turing machine. Is it true that the same program $P$ with input $F(i)$ also halts (or not, respectively), where $F$ ...
0
votes
0answers
26 views

Why is $DSPACE(\log(n)) = NSPACE(\log(n))$ not known?

Here $DSPACE(\log(n))$ is the family of algorithms for which there exists a deterministic Turing machine using $O(\log(n))$ space. On the other hand $NSPACE(\log(n))$ is the family of algorithms for ...
0
votes
0answers
42 views

Universal Turing Machine run on Universal Turing Machine

I am curious, what happens if we run Universal Turing Machine on itself?
0
votes
1answer
67 views

Deciding whether set of running times is infinite

I have a language $\mathrm{Count}(M)$, defined below, and a finite number $k$. \begin{align} \mathrm{Count}(M)= \{k \in \mathbb{N} \mid \text{there exists some input on which $M$ halts after exactly ...
0
votes
1answer
63 views

Doubt regarding Cantor's diagonalization argument [closed]

So, we use Cantor's diagonalization argument to prove that the Universal Turing Machine is not a decider. I understand the overall argument but have a problem regarding one caveat mentioned in my ...
1
vote
1answer
24 views

Simulations between Turing machines

I've got a question. How can i simulate Turing machine with a double-sided infinite tape by a Turing machine with one-sided infinite tape? The condition is, that the simulation of one step of the ...
3
votes
1answer
42 views

motivation and idea of defining non-deterministic Turing machine

This is a very basic question but I spent some time reading and find no answer. I am not computer science majored but have read some basic algorithm stuff, for example, some basic sorting algorithms ...
1
vote
2answers
47 views

Proving the decidability of whether a CFG generates a particular string or not

Let $G$ be a context-free grammar and $w$ be a string of length $|w| = n$. Consider the language $A_{CFG}$ = { <$G$, $w$> | $G$ is CFG that generates $w$ }, where <$G$, $w$> is a string ...
1
vote
1answer
28 views

High-level description of aTM

If I have language: L = {x | x = n^2 for some integer n} How can I give a high-level description of Turning Machine that decides on the language?
0
votes
1answer
49 views

Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1?

Consider the function $f$ that maps strings over $\{a, b, c\}$ to strings over $\{0, 1\}$ by replacing each $a$ by 0, each $b$ by 0, and each $c$ by 1. For example $f(cabbc) = 10001$. The function $f$ ...
1
vote
1answer
48 views

How can I show that a language is Turing-recognizable and decidable?

I was wondering how I can show that the language $\{a^n b^n c^n \mid n \geq 0 \}$ is Turing-recognizable. Also, if it is Turing-decidable?
1
vote
1answer
40 views

Give an implementation leveldescription of a TM

L = {x=y ⊕ z|x, y, z are binary integers, and x is the XOR of y and z} is non-regular, i.e., no FA exists that could recognize the language. How can I give an implementation level description of a TM ...
0
votes
1answer
69 views

Reducing the halting problem for a language with strings that include at least one 1

$L_1$ = A sequence of $0$ or $1$'s such that at least one $1$ is in the sequence $L_2$ = Turing machines that decide $L_1$ I think the first language is decideable, as the input string is of finite ...
0
votes
1answer
126 views

Turing Machine to return all prime numbers

My task is to design Turing Machine that ignores its input and returns all the prime numbers. I have some basic idea how to do that but I am not completely sure whether my approach is correct or not. ...
0
votes
2answers
58 views

Turing machine that applies homomorphism on input string

I really need some help with this problem. I'm running into the issue that the input is running out of space to append the 11 or 10. I could really use some help conceptualizing this problem and how ...
-1
votes
0answers
42 views

Turing machine; theory of computation

I'm trying to build a deterministic Turing machine that takes 2 words $w_1, w_2 \in \{a, b, c, d\}^*$ separated in the form of $Bw_1\#w_2B$ and determine whether $w_2$ is a substring of $w_1$. The ...
2
votes
0answers
12 views

Similarities between Babbage's difference engine and the Turing machine

What would you consider similarities between the difference engine and the Turing machine? At this point I feel I know how they both function, yet I can't point out any worthwhile similarities between ...
-6
votes
0answers
53 views

Halting problem proof is wrong, here is why

Instead of solving the halting problem, I will try to solve a less complicated problem in a similar manner. Can we write a function that will predict if two given numerical inputs are equal. I will ...
0
votes
1answer
55 views

Decidable questions of undecidable problems

Even if there is no general algorithm to decide if any program will halt, but there could be properties or meta-questions about the programs that is decidable. For example, given program $A$ and a ...
1
vote
1answer
32 views

Is it possible for a Turing machine to halt without reading the complete input string?

Is it possible for a Turing machine to halt without reading the complete input string. Suppose there is a string "adc" preceded and succeeded by infinite number of blanks. Can a Turing machine halt ...
-1
votes
1answer
40 views

How to construct a Turing Machine

Can someone help me to write a Turing Machine that decides whether its input sentence is in a particular language or not? This particular language generates alternating 01's. If it decides the input ...
2
votes
1answer
34 views

Showing the following language is decidable

Let $BAL_{DFA} = \{<M> \mid M \text{ is a DFA that accepts some string containing an equal number of 0's and 1's } \}$ Show that $BAL_{DFA}$ is decidable. Generally such questions seem to be ...
1
vote
1answer
22 views

Showing the language of TMs that halt on a decidable set of words is not in RE

I need to show that the following language, L = {$\langle M \rangle$ | The set of words which M halts on is decidable}, is not recursively enumerable. In the instructions they advise thinking of a ...
0
votes
0answers
41 views

Head Position Function of Oblivious Turing Machines

I am trying to understand oblivious Turing machines. According to the book of Arora and Barak, a TM $M$ is oblivious if the location of each of its heads at the $i$-th step of execution on input $x$ ...
1
vote
1answer
64 views

How to find out the complement of a language of turing machines?

With only using our thinking. What do I have to think about when finding a complement of a Turing machine for example. L={M∣M is a TM that halts on empty tape after even transition steps} What's the ...
1
vote
1answer
22 views

Equivalence from multi-tape to single-tape implies limited write space?

Suppose I have the following subroutine, to a more complex program, that uses spaces to the right of the tape: $A$: "adds a $ at the beginning of the tape." So we have: $$ \begin{array}{lc} \text{...
0
votes
1answer
41 views

Is language {M | M halts and print “Hello World”} recursively enumerable?

Is language {M | M halts and print "Hello World"} recursively enumerable? I'm not sure my proof is correct. Let universal Turing machine U start another Turing machine M2 that reads result of work of ...
3
votes
2answers
127 views

What can't you do without Turing-completeness?

I suppose that, since a Turing-complete language can simulate a Turing-machine, a non-Turing-complete language can't, but most programs do not have the simulation of a Turing machine as their purpose. ...
0
votes
0answers
16 views

Functions cumputable in $\theta(n)$ and $\theta(|S| \cdot n)$ for calculating subsets of size |S|

I need to define a function $f: \mathbb{N} \rightarrow \{0,1 \}$ that is computable (by a deterministic TM) in $\theta(n)$ worst case time and such that the time complexity for calculating $f(S)$ is $\...
0
votes
1answer
929 views

Class of languages recognised by a Forgetful Turing Machine

A Forgetful Turing Machine (FTM) operates just like a normal Turing machine except that, in every instruction (i.e., transition), the letter written in the tape cell is always the letter $a$, ...
0
votes
1answer
33 views

I want to know where there is the flaw in my argument

I came across following problem to finding whether the following language is decidable or semi-decidable or not even a semi-decidable. $L: \{\langle M\rangle: M\space is\space a\space TM\space and\...
5
votes
2answers
1k views

How is the problem, {⟨G⟩|G has no triangle} in Logspace?

I read this problem as a part of my course curriculum, in my professor's notes. I am not able to understand about the standard solution, that if I list all the possible triplets of vertices as 3-...
-1
votes
1answer
67 views

Why is it not possible to prove that two Turing Machines calculate the same function?

I was wondering why it is not possible. Is it because the corresponding language is not decidable, or because of the fact that it is not guaranteed that a Turing machine halts on every input?
0
votes
0answers
49 views

Why is it not possible to prove the equivalence of nondeterministic and deterministic Turing Machines the same way as for NFAs and DFAs?

I found en excercise asking this question. I know that for proving the equivalence of NFAs and DFAs we can use the conversion through subsets, and that for proving the equivalence of nondeterministic ...
1
vote
1answer
49 views

How can $A \cup B$ be decidable if $B$ is undecidable?

My assignment says: "Determine if the following statement is correct: If $A$ and $A \cup B$ are decidable, then $B$ is decidable." The solution says: "Incorrect. If $B = H_0 \subseteq \{0,1\}^*$ ...
1
vote
0answers
115 views

Proof by reduction and Turing machines [closed]

This is a practice question I have, but I can't wrap my head around it. ............. Let L = {M | M is a TM that halts with exactly two words on its tape in the form Bw1Bw2B}. B = Blank Position the ...