Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
2,490
questions
-1
votes
0
answers
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.
0
votes
1
answer
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\}^*$ ...
- 3
1
vote
1
answer
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....
- 31
0
votes
1
answer
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 ...
- 11
1
vote
2
answers
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 ...
- 11
0
votes
0
answers
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 ...
0
votes
1
answer
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. ...
- 3
0
votes
1
answer
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 ...
0
votes
0
answers
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 ...
- 229
0
votes
1
answer
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 ...
- 11
1
vote
1
answer
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$...
- 11
1
vote
1
answer
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 ...
0
votes
0
answers
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 ...
0
votes
0
answers
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 ...
- 101
0
votes
1
answer
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. ...
0
votes
0
answers
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.
...
- 101
0
votes
1
answer
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
1
answer
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 ...
- 11
1
vote
0
answers
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 ...
- 11
1
vote
1
answer
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 ...
- 177
-3
votes
1
answer
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 ...
0
votes
2
answers
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 ...
- 101
-1
votes
2
answers
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 ...
- 1
4
votes
3
answers
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 ...
- 51
-6
votes
1
answer
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 ...
- 11
1
vote
4
answers
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 ...
2
votes
2
answers
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 ...
- 123
0
votes
2
answers
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?
- 3
0
votes
2
answers
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
1
vote
0
answers
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 ...
- 11
0
votes
1
answer
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 ...
- 101
1
vote
1
answer
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 ...
- 11
1
vote
0
answers
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). ...
- 111
0
votes
0
answers
75
views
Proving EXP-Completeness for the Bounded Halting Problem
I am currently working on proving that the bounded halting problem is $EXP$-Complete. The bounded halting problem is defined by the language $L$ as follows:
$$L = \{\langle M,x,t \rangle : \text{...
0
votes
0
answers
14
views
Computational power of Turing machines vs circuit ensemble
Is it true that for every Turing machine 𝑀, there exists a circuit ensemble 𝐶 such that 𝐿(𝑀) = 𝐿(𝐶), or is it true that for every circuit ensemble 𝐶, there exists a Turing machine 𝑀 such that �...
0
votes
2
answers
106
views
Why is the Turing machine model relevant?
I am learning about computational models, I wonder why Turing chose his model of Turing machines (the strip with the head and Read / Move left or right / Change state).
I am suspecting his physical ...
- 101
0
votes
1
answer
402
views
TMs can decide whether or not a string is a Palindrome, yet, the language called PALINDROMES is undecidable - why?
I came across this language, where M denotes a Turing Machine:
PALINDROMES $:= \{M \mid M \text{ accepts strings which are palindromes}\}.$ It is proven to undecidable.
And, I know one can construct a ...
0
votes
0
answers
59
views
Has a Multitape Machine like this been Studied?
Sometimes as a hobby I like to think about different possible "fundamental" abstract computing frameworks, akin for instance to Turing Machines and Lambda Calculus. In particular, I've been ...
-1
votes
1
answer
32
views
Need help with a proof: L is recursively enumerable if and only if L is Turing recognizable
I am unable to understand this proof
L is recursively enumerable if and only if L is Turing recognizable
If anyone can prove this, that would be great help
- 1
0
votes
0
answers
22
views
Why nondeterministic decider for $ HAMPATH $ runs in polynomial time?
( Source: Introduction to the theory of computation, Michael Sipser, 3rd edition )
I know the computation-time of a non-deterministic Turing machine ( NTM ) which is a decider is defined to be the ...
- 233
0
votes
0
answers
94
views
Turing machine for unary subtraction $m-n$. If $m<n$, the machine writes "$!$" $|m-n|$ times
I am trying to program a Turing machine that performs unary subtraction, $m-n$, but if $m<n$, the machine writes the $!$ symbol on the tape $|m-n|$ times. If $m=1$ and $n=3$, the machine would only ...
- 101
0
votes
0
answers
26
views
$FINITE_{TM}$ is not Turing-reducible to $A_{MT}$
$FINITE_{TM} = \{\langle M \rangle\mid M\text{ is a TM and }L(M)\text{ is finite}\}$
$A_{MT} = \{\langle M,w \rangle \mid M\text{ is a TM and }M\text{ accepts }w\}$
I'm trying to prove that $FINITE_{...
0
votes
1
answer
46
views
Reduction from a language with unknown decidability to HALT
We were taught to use reductions in order to show that a given L is undecidable. My question is, given some definition of a new L, is there a way to find a reduction
$$
L\leq_mHALT
$$
So that I can ...
- 1
2
votes
2
answers
216
views
Turing machine that splits a string into 3 equal parts in $O(n\log n)$
I have the following question: given a string $X^n$, where $n$ is divisible by $3$, how to build a one-tape Turing machine with complexity $O(n\log n)$ that splits this string into $3$ equal parts?
I ...
0
votes
0
answers
16
views
How to construct an f-Timer
I am trying to costruct an $f$-timer for the function $f:\mathbb{N}\rightarrow\mathbb{N}: x\mapsto \lfloor cx^2\log x\rfloor$ for a proper constant $c>0$; so I need a TM that for every input of ...
- 1
3
votes
1
answer
2k
views
Is a machine Turing-complete when it can decide a context-sensitive language?
If a machine can decide a context-sensitive language (like the language of palindromes with a non-linear center) is that fact a proof that the machine is Turing-complete?
Can this be used to prove ...
- 155
1
vote
1
answer
50
views
Semi-decidability of Fullness problem for Turing Machines
Input: code $u$ of a Turing Machine working on a binary alphabet.
Question: Does $M_u$ accept all words $w \in \{0,1\}^*$.
This is of course an undecidable problem. I wonder if the problem is semi-...
- 13
1
vote
0
answers
28
views
Non-Deterministic Turing Machine That Accepts RE-R language
As far as I know for Non-Deterministic Turing Machine (NTM) there are 4 kind of branches:
An input is accepted if there is at least one node in the tree that is an accept.
An input is rejected if all ...
- 11
0
votes
0
answers
46
views
Is the $Even - Halt$ problem decidable?
Is the language:
$$L = \{\ \langle M \rangle \ |\text{ There is an input $w$ such that M performs even number of steps before M halts on $w$} \}$$
They way I approached the problem the was the ...
0
votes
0
answers
39
views
Busy Beaver non-computability proof by contradiction
When proving the non-computability of the Busy Beaver function by contradiction, people create machines that are able to calculate the Busy Beaver function, BB(n), and also write more than 1s than BB(...
- 101