# Questions tagged [turing-machines]

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

2,490 questions
Filter by
Sorted by
Tagged with
18 views

### How to construct a turing machine from L= {w (a Ub)* | w = wR} [closed]

How to construct a Turing machine from L= {w (a Ub)* | w = wR} . I have to design a Turing machine in exam. help me.
23 views

### $NL$ Leaf languages and $PSPACE$

I am reading Papadimitriou's Computational Complexity and got stuck on part d) of the following exercise (pg. 505) 20.2.14 A panorama of complexity classes. ... A language $L \subseteq \{0, 1\}^*$ ...
1 vote
59 views

### If NP $\subset$ BPP, then NP $\subset$ RP. Confusion about the correctness of Probabilistic Turing Machine

I found the proof of this theorem from https://www.csie.ntu.edu.tw/~lyuu/complexity/2011/20120103s.pdf. Here is the screenshot of the construction of probabilistic Turing machine RP. (https://i.stack....
19 views

### Why is $DSPACE(\log^2n)\subseteq DTIME(n^{\log n})$?

I am having trouble with the statement that $DSPACE(\log^2n)\subseteq DTIME(n^{\log n})$ holds which is given without argument in the paper The structure and complexity of minimal NFA's over a unary ...
1 vote
43 views

### In the simulation of a C-program by a Turing machine, how does a TM determine which instruction to execute?

In Arora-Barak, the authors mention a way how TMs can compute everything that can be computed by computers. The idea is that every high-level language program has an equivalent machine language ...
19 views

### Does valid value in L2 have to be gotten from L1 when we have a Many-One Reduction from L1 to L2

If I am doing a many-one reduction from L1 to L2, since it is described as a total function, does that mean that every possible encoding in L2 should have been achieved from L1 or is it possible that ...
28 views

### Can an unreocognizable language be Turing-reducible to a recognizable language?

Suppose $L_1\preccurlyeq_T L_2$, and $L_1$ is unrecognizable, can $L_2$ be recognizable? With decidability, if $L_1$ is undecidable, then $L_2$ is undecidable, because $L_1$ is the “easier” question. ...
43 views

### Informal description of Non-deterministic TM for the language $L = \{w^n \mid w \in \{a, b\}^* \text{ and } n \geq 2\}$

From a list of practice problems for a graduate Theory of Computation course. I've done quite a few problems at this point on deterministic Turing Machines, I just don't think I have fully grasped the ...
48 views

### Non-deterministic Turing machine that decides the language $L = \{0^{n^2} | n \geq 1\}$

I was trying to figure out how can I construct a non-deterministic Turing machine that decides the language $L = \{0^{n^2} | n \geq 1\}$ I looked at some of the proposed solutions here : Turing ...
57 views

### Turing machine comparing two binary numbers in linear time

I was wondering how you would go about making a two-tape Turing machine in linear time that starts with input 𝑥#𝑦 on Tape 1, where 𝑥 and 𝑦 are binary integers that might have leading 0's. It would ...
1 vote
30 views

### Showing SAT is auto-reducible

I am trying to wrap my head around the concepts of auto-reducibility and having access to an Oracle. The way I understand is that a language is auto-reducible iff there is a Turing Machine $M^{L}(x)=1$...
1 vote
35 views

### Complexity of simulations in simulations

This video of a group, who simulated (a very simple version of) Minecraft inside Minecraft itself got me thinking about the performance of such setups. Another example to what I'm referring to, would ...
22 views

### If we have two TMs D1 and D2 and the languages of the TMs L(D1) != L(D2), then is this problem decidable/recognizable? [duplicate]

We know that in the case where, L(D1) = L(D2), the problem is undecidable. But what happens when the languages are not equal? I would assume it's still undecidable, but is it recognizable? And how ...
49 views

### Turing machine for a^n b^m c^n d^m

The state diagram for the initial part of this turing machine given as: Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' to X2. After that we go back ...
48 views

### A program that solves the Halting Problem for programs with N states

My question relates to the conclusions drawn from the Halting Problem. I understand that the Halting Problem proves that no program H(P,i) exists that determines if P(i) halts or not for P in general. ...
44 views

### Is computation of a given operation infinitely multiply realizable 'computationally-speaking'?

This is a somewhat philosophical question, but I would like to know if there is a hard answer. Also, please excuse my likely unconventional terminology here, this is not my field of expertise. ...
41 views

### how do universal turing machines actually work

a TM has states and a tape, and a set of symbols that can get put on the tape. when it 'reads' a symbol on the tape, it's current 'state' tells it what to do next; write a new symbol, where to move ...
1 vote
41 views

### How to formally show computational equivalence or universality using encodings?

I want to formally show that a computational system $\mathcal M$ is computationally universal by showing it is computationally equivalent to some already known universal system, i.e. some UTM. To show ...
1 vote
20 views

### Is it possible for a Linear bounded automaton to be a recognizer but not a decider?

So we know that LBAs have a finite number of configurations, which makes the task of detecting loops much easier. My proposition is that if a given LBA is constructed to recognize a language, it also ...
1 vote
54 views

### Are there situations where we can decrease the time complexity of a program by increasing its ordinal complexity?

Are there (interesting) situations where we can decrease the time complexity of a program by increasing its ordinal complexity? For example, is it possible to find a primitive recursive function such ...
78 views

### Can a decider return "Undecidable" on the Halting Problem? [closed]

So, I know there is no general algorithm for the halting problem, but I was curious if a three output decider could at least give us "an" output {0 if doesn't halt, 1 if halts, U if ...
52 views

### Why there can't be two instances of a "reverse" program in the Halting problem?

So in the halting problem, there is a program that reverses the output of a program that tells if the input program halts or runs forever(I'll call it the main program further). The whole paradox is ...
49 views

### Show that the language is undecidable

Consider the language L = {< M >| M accepts iff input length is divisible by 3}. I'm supposed to use reduction to show that the language is undecidable. I tried proving it but didn't know what ...
1k views

### Are 2 independent PDAs equivalent to a turing machine?

I was thinking about the language $a^nb^nc^n$, which is obviously not context free, but if we run it through 2 automata at the same time (the first for $a$ and $b$ and the second for $b$ and $c$ and ...
55 views

### Is ChatGPT wrong about the definition of unrecognizable and undecidable languages?

I asked ChatGPT to give me the difference between unrecognizable and undecidable languages, and this what it gave me: Unrecognizable languages can be accepted by a Turing machine, but the machine may ...
1 vote
3k views

### Can we ever achieve Turing completeness?

I want to relate Turing completeness to the Halting Problem. As far as I know we say something is turing complete (eg: a programming language) when it can compute any function and can do any task. But ...
123 views

### What are quines (layman friendly)?

I was going through the Wikipedia page on Quines and did not understand this paragraph - A quine is a fixed point of an execution environment, when the execution environment is viewed as a function ...
58 views

### How to prove that the subset of a language L that is in P is also in P?

Given that $L∈\textrm{P}$, how do we show that an arbitrary subset $L_{A}$ of $L$ is also in P?
61 views

### Infinite Recursion as the Intuitive Foundation for the Halting Undecidability Proof

all, I was wondering if my intuitive understanding of why the halting problem is undecidable is actually correct? TLDR: Halting problem is undecidable because it leads to infinite recursion and never ...
1 vote
34 views

### Loop-Program possible modifications

Recently learning some core register modifications and made a loop-program that calculates the gcd. Any way to improve/shorten this version I came up with? Input for x and y go into x1 and x2 and ...
20 views

### Is the Busy Beaver with n states also the busiest Turing machine (counted in steps) with n states?

Based on the Busy Beaver rules (2 letter alphabet, 2-way unbounded tape, program must halt, etc) I was wondering if the Busy Beaver for each n is also the program that does the most steps, or if there ...
1 vote
163 views

### What could $P = NP$ imply about arbitrary Turing machines?

My question: What $P \not= NP$ or $P = NP$ could imply about arbitrary Turing machines and arbitrary computations? I assume that a partial and incomplete, but objective answer to this question exists ...
1 vote
26 views

### Can a modified Turing Machine be Turing-Complete if its Program and Data memory share the same tape?

I've been working on a fun esolang that operates under the idea that it only has program memory (an infinite, sequential list of registers that instructions and instruction arguments are loaded into). ...