# Questions tagged [turing-machines]

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

1,660 questions
Filter by
Sorted by
Tagged with
8 views

### Maximum Query String Length in Oracle Turing Machines

I am learning oracle Turing machines, which is normal Turing machines equipped with a write-only query tape and with access to a query oracle. My question is, is there a limit of the content that can ...
24 views

### Turing Machine where the number of a’s and b’s are either both even or both odd over {a,b} [closed]

Turing Machine where the number of a’s and b’s are either both even or both odd.
20 views

### decidability and reducibility

I am a bit confused on how I can show the finiteness problem is undecidable using Rice’s Theorem. So I’ve got something like B = { | M is a TM and L(M)- finite}. I thought I could reduce A TM (...
9 views

### Improving Turing Machine for Eulerian Path Problem [closed]

I'm trying to construct a determinististic one-tape Turing Machine for an Eulerian Path (https://en.wikipedia.org/wiki/Eulerian_path). I have written the one below as a starting point, but would like ...
21 views

### Question for “Only if” part for the theorem “A language is Turing-recognizable iff some enumerator enumerates it.”

I am trying to prove the theorem A language is Turing-recognizable iff some enumerator enumerates it. I proved the "if" part, but I have no idea of proving the "only if" part, so I searched a ...
42 views

### Does any algorithm loops at some point?

Given that any implementable algorithm has a finite number of internal states, and given that any state is determined by the previous one, does that implies that any algorithm loops at some point? If ...
35 views

55 views

25 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$ ...
17 views

### Design a Turing machine that accepts L={ww^r | w:(0,1)*}?

Can anyone help :( L = {ww^r | w element of (0,1)*} Would it be like in :pseudo code, check if the string is equal to itself in reverse?
51 views

### Converting from m base to n base without arithmetic operations (Where m<n )

I have been working the last 8 years in try to convert from base n to base m without artihmetical operations. My hypothesis is that by the same way that is possible convert bases without division (...
17 views

### Prove undecidability of a TM M that accepts at least one input AND rejects at least one input

I got stuck trying to prove that AND statement. I assumed that the TM will accept if its language is not empty and the complement of its language is not empty and reject if its language is empty or ...
22 views

### Bounds on tape alphabet size of a Turing Machine encoding

What is the max possible ratio between the tape alphabet size and the total encoding size in an asymptotic sense? Say if I take some TM and add more and more symbols to its tape alphabet, will the ...
15 views

### Correct Turing machine representation for Rice Theorem proof

Consider the language L1. From Rice Theorem I know L1 is not decidable (i.e. undecidable). L1 = { R(M) | R(M) is a TM and 1011 ∈ L(M)} For example if I want to represent by diagram a TM $M_1$ ...
10 views

### Decide if Turing machine's language contains either a or b string

during school exercises we worked on decidability problems and there was one I don't really understand. We were provided with solution and explanation regarding this exercise but still I need more ...
26 views

### A TM that doesn't decide Σ*, and a TM that doesn't decide the empty set?

I was wondering if it was possible to create a TM that semi-decides (but doesn't decide) either of the following two languages: $\emptyset$ $\Sigma^{*}$ I assume for 2, a one-state TM that just ...
13 views

### TM decidable or undecidable problem

Problem: Given a TM $M$ on the alphabet $\{0,1\}$, determine if there is some input on which $M$ executes for at least 5 steps. Is this problem decidable or not? To check if the problem is ...
42 views

### Why can't we prove decidability of $L= \{ \langle M \rangle : M$ accepts $\epsilon \}$ with a configurations graph?

Since every deterministic Turing Machine can be translated to a graph of configurations such that $M$ accepts a word $w$ iff there is a path from the initial configuration that matches $w$ to an ...
103 views

### Is it decidable “Given a TM M, whether M ever writes a non blank symbol when started on the empty tape.”

I came across below problem in this pdf: Given a TM M, whether M ever writes a non blank symbol when started on the empty tape. Solution given is as follows: Let the machine only writes blank ...
40 views

### Analogue of the topology-computability correspondence for computational complexity

There is an interesting correspondence between notions of topology and notions of computability theory originating from the ingenious idea of Dana Scott to identify computable functions with ...
19 views

96 views

### Example of two undecidable languages that cannot be reduced to each other

I want to find two undecidable languages $A$ and $B$ that $A$ cannot reduce to $B$, $B$ cannot reduce to $A$(Many-one reduce). One of my thought is to let $A$ be the halting problem, let $B$ be some ...
56 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$ ...
151 views

### Is it possible that the subtraction between two undecidable languages is regular?

If $L_1$ and $L_2$ are both non-decidable languages (Not decidable, so can be SD or $\lnot$SD), is it possible that $L_1-L_2$ is regular and $L_1-L_2\neq\phi$, where $\phi$ is the empty set? What's ...
781 views

### Why it is said that LBA is a non deterministic Turing Machine

I have read that linear bounded automaton is a Non deterministic Turing machine. Why is it so?
10 views

### time complexity turing machine equal to “n + 1”

I have not clear why the time complexity is n+1 and not n+2. Consider a TM with a single tape and alphabet {0,1} and the string | * | 0 | 1 | 1 | 0 | 1 | 0 | * | ...
36 views

### turing machine logic instead of something

Lets assume I have this turing machine: And I have a $\Sigma = \{0,1,2,3,4,5\}$. Now my question is can I simplify the transaction from $A$ to $B$ ? Is there any way so I can write - when the read ...
16 views

### variable in turing machine

Here is a simple turing machine, that accepts only $0$. For this, it read $0$, write it with $x$, then move to right and checks end, if it is end it accepts. With that logic, I can also add this <...
80 views

### Can I apply Rice's theorem to decide decidability status of these languages?

I came across these languages: A Turing machine prints a specific letter. A Turing machine computes the products of two numbers I was guessing whether I can apply Rice's theorem to decide upon above ...
77 views

### Why Rice theorem work for decidability?

Rice's theorem states: Every nontrivial property of recursively enumerable language is undecidable. I came across following problems, which Ullman's books say both are undecidable: Turing ...
51 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 ...
53 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 ...
20 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, ...
50 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...
52 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 ...
58 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 ...
33 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 ...
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), \\ ...