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
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 ...
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), \\ ...
-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
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 ...
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 ...
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
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
0
votes
1answer
118 views

A language which is neither r.e. nor co-r.e

First, consider $$L_\exists=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts some input}\}$$ is RE. I tried to construct a Turing machine: ...
3
votes
1answer
152 views

Can an alphabet for a Turing machine contain subsets of other alphabets?

For example; Is {0,1,{a,b,c},d,e} a valid alphabet to form a language over and is it usable in any context?
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 ...
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 ...
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
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 ...
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 ...
0
votes
1answer
68 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
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
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?
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
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. ...
2
votes
1answer
69 views

Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times

I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation"). Can I just use ...
2
votes
1answer
39 views

How To Show That B is Semi-Decidable Given A

I am preparing for my Computational Theory final and ran into this exact problem : B={ x | there exists a prefix of x that is in A}. Show that B is semi-decidable. In other words, you need to ...
-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 ...
0
votes
1answer
104 views

Why is a subset of a undecidable language decidable?

I have problems with the understanding why a subset of a undecidable language is decidable. We've proved in the lecture that $HALT$$_T$$_M$$=${$<M,w>$|M is a TM and M halts on input w} is ...
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 ...
3
votes
2answers
317 views

Proof that Turing machines and computers have same power

How do we prove that any logical circuit can be simulated by a Turing machine? For example, we take a logical circuit $L$ that is made of gates and, or, and not. This circuit determines a problem, ...
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 ...
0
votes
1answer
70 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 ...
0
votes
1answer
87 views

Rice Theorem - Problem to understand and apply it

I have struggle to understand the Rice Theorem. My understanding of Rice Theorem: The purpose of this Theorem is to proof that some given language L is undecidable iff the language has a non-trivial ...
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. ...