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
-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.
Phone Myint Zaw's user avatar
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\}^*$ ...
KJL's user avatar
  • 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....
ltl's user avatar
  • 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 ...
Yannik Eik's user avatar
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 ...
Burt Macklin's user avatar
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 ...
River Uzoma's user avatar
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. ...
Arthur's user avatar
  • 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 ...
codeing_monkey's user avatar
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 ...
Yarin's user avatar
  • 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 ...
Alex's user avatar
  • 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$...
Meki21's user avatar
  • 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 ...
SmallestUncomputableNumber's user avatar
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 ...
Luis Ramirez's user avatar
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 ...
Tanuj's user avatar
  • 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. ...
Vincenzo Buselli's user avatar
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. ...
clayton groth's user avatar
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 ...
gangsterio's user avatar
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 ...
Yannik Eik's user avatar
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 ...
Aland Ameer's user avatar
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 ...
agemO's user avatar
  • 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 ...
Daniel Stilman's user avatar
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 ...
YKY's user avatar
  • 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 ...
berlin23's user avatar
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 ...
Bogdan's user avatar
  • 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 ...
Aland Ameer's user avatar
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 ...
D Star Let's Explore's user avatar
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 ...
DashwoodIce9's user avatar
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?
Ke Cheng's user avatar
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 ...
boinka's user avatar
  • 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 ...
Zamira Zamba's user avatar
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 ...
sh1mmer's user avatar
  • 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 ...
Axid Ubish's user avatar
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). ...
Charles Averill's user avatar
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{...
Straw User's user avatar
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 �...
Noah Carter's user avatar
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 ...
NotaChoice's user avatar
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 ...
HaferFlockenPengu's user avatar
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 ...
user1609012's user avatar
-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
Henry's user avatar
  • 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 ...
flamel12's user avatar
  • 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 ...
l0ner9's user avatar
  • 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_{...
Laurus Laurus's user avatar
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 ...
John's user avatar
  • 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 ...
Vandiscleisson N.'s user avatar
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 ...
Leo's user avatar
  • 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 ...
Barney's user avatar
  • 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-...
Stanley's user avatar
  • 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 ...
Yuval's user avatar
  • 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 ...
Giorgos - Marios Patelis's user avatar
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(...
user3348949's user avatar

1
2 3 4 5
50