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
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 ...
-1
votes
0answers
24 views
0
votes
0answers
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 (...
0
votes
0answers
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 ...
1
vote
2answers
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 ...
2
votes
2answers
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 ...
2
votes
1answer
35 views

Proof that $(L_{all})^C$ is not recursively enumerable

The problem: We have the language $L_{all} = \{\operatorname{Kod}(M) | M \text{ is a turing machine and } L(M) = \Sigma ^*\}$ Hence, $L_{all}$ is the set of all encoded Turing machines (the $\...
3
votes
2answers
62 views

Can a Non-Deterministic Pushdown Automaton recognize $ \# a^nb^{2^n} \# $ which a TM can?

$ \# a^nb^{2^n} \# $ such that • The alphabet of the machine is {, a, b, x}. • The symbol x will never appear on the input a. • The contents of the tape at completion may be anything. • The head ...
0
votes
1answer
29 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 ...
1
vote
1answer
34 views

How to translate automaton (Turing machine) into the program of high level programming language?

Every program in high level ("industrial") programming language can be expresses as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the Cartesian ...
55
votes
7answers
12k views

Are there minimum criteria for a programming language being Turing complete?

Does there exist a set of programming language constructs in a programming language in order for it to be considered Turing Complete? From what I can tell from wikipedia, the language needs to ...
1
vote
1answer
50 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 ...
4
votes
1answer
720 views

How to simulate a bidirectional TM on a regular one with time factor four?

In Computational Complexity A Modern Approach, one claim says that if $f$ is computable in time $T(n)$ by a bidirectional TM $M$, then it is computable in time $4T(n)$ by a unidirectional TM $\tilde{M}...
0
votes
1answer
55 views

Some questions about the Computability of Turing Machines

I'm learning for a test and I have some important questions about Computability of deterministic and non deterministic Turing Machines. Consider we have the partial functions $f,g,h,t: \mathbb{N} \...
1
vote
0answers
28 views

Is ASM a regular language?

I'm giving a presentation where I have a single slide dedicated to formal languages. In this slide I give a simplified overview of the Chomsky Hierarchy and I'd like to give an example of a real world ...
2
votes
1answer
65 views

If A and B are NP-complete, then A ∪ B need not be NP-complete

I am studying the proof of this exercise (link) There exist N P-complete languages A and B such that A ∪ B is not N P-complete. Example: $A = \{1x : x ∈ SAT\} ∪ \{0x : x ∈ \{0, 1\}^∗\};$ $B =...
0
votes
1answer
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$ ...
0
votes
1answer
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?
2
votes
0answers
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 (...
0
votes
0answers
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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$ ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
5
votes
0answers
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 ...
0
votes
0answers
19 views

Binary code of universal Turing machine which accept word w = aba

$⟨M⟩$ is code of Turing machine and $⟨w⟩$ is code of word w. Find binary code of universal Turing machine which accept word w = aba. Could I use Turing machine deciding $L = \{w ∈ \{a, b\}^*\ |\ |w|\ ...
-1
votes
0answers
33 views

Turing machine deciding $L = \{w ∈ \{a, b, c\}^*\ |\ |w|\ mod\ 3 = 0\ OR\ w ≠ w^R\}$

$$L = \{w ∈ \{a, b, c\}^*\ |\ |w|\ mod\ 3 = 0\ OR\ w ≠ w^R\}$$ I'm looking for transition function... Any hint?
3
votes
1answer
52 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 ...
0
votes
2answers
44 views

Halting problem vs Universal Language

Wikipedia defines halting set as follows: $H = \{(i, x) |$ program $i$ halts when run on input $x\}$ Ullman defines universal language as follows $U = \{(M, w) |$ Turing machine $M$ accepts $w\}...
2
votes
1answer
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 ...
0
votes
1answer
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$ ...
3
votes
3answers
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 ...
-3
votes
2answers
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?
0
votes
0answers
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 | * | ...
1
vote
2answers
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 ...
1
vote
1answer
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 <...
1
vote
2answers
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 ...
-2
votes
2answers
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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, ...
0
votes
1answer
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...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
38 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), \\ ...