Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [turing-machines]

The Turing machine is a fundamental model of computation, especially in theoretical work.

Filter by
Sorted by
Tagged with
-1 votes
0 answers
65 views

Halting problem corresponds to incompletness theorem, what problem does correspond to the independence [closed]

We know by self-reference, halting problem corresponds to the incompletness theorem of first order Peano arithmetics, what problem of Turing Machine does correspond to the independence of Euclidean ...
XL _At_Here_There's user avatar
1 vote
0 answers
77 views

Planar Turing Machine with (relatively) Small Alphabet

There is a simple construction that takes any drawing of a Turing Machine in the plane and outputs another planar, equivalent one with a "small" blowup in the number of states, and only two ...
Ryan Dougherty's user avatar
1 vote
1 answer
99 views

Turing 1936 Skeleton Tables Procedure

I am reading Turing 1936 to learn about the halting problem from its origin. However, I encountered a roadblock upon reaching section four, in which Turing demonstrates that his m-configuration tables ...
Missingno's user avatar
3 votes
0 answers
81 views

Complexity of chess with 50-move rule

It is known that evaluating who wins in $n \times n$ chess positions is EXP-complete (and thus unconditionally not in P), and this effect is due to the game having rich possibilities for exponentially ...
Alexey Slizkov's user avatar
8 votes
1 answer
243 views

Is any function between $n$ and $n\log n$ time-constructible on a 1-tape TM?

The question: Is there an $f$ in $\omega(n) \cap o(n \log n)$ that is time-constructible on a 1-tape DTM? I.e. $f$ such that $\lim_{n\to\infty} \frac{n}{f(n)} = \lim_{n\to\infty} \frac{f(n)}{n \log n} ...
Neal Young's user avatar
  • 10.8k
-1 votes
1 answer
82 views

The role of Turing machines in computational complexity [closed]

In the popular book "Introduction to algorithms" by CLRS even though rigorous proofs are given about the complexity analysis of algorithms there is no mention of Turing machines. Instead ...
Sanyo Mn's user avatar
1 vote
2 answers
342 views

Nondeterministic Turing Machines as deciders, versus NP and co-NP

While preparing a class, I stumbled over a point that I could not elucidate. Explaining it requires a few step. Deciding vs Recognizing: A Turing machine $M$ decides a language $L$ if whenever $s\in ...
Arnaud Casteigts's user avatar
3 votes
1 answer
246 views

Complexity of determining whether the language of an P machine is empty

Suppose you are given a deterministic Turing machine and you are guaranteed it runs in polynomial time. What's the computational complexity of determining whether the language accepted by the machine ...
user1868607's user avatar
  • 1,019
2 votes
1 answer
152 views

Self-universality and Turing-completeness

By definition, any formal system (machine, language, etc.) that can compute (simulate) any Turing machine or its equivalent (lambda calculus, recursive functions, etc.) is Turing complete. I wonder if ...
Barney's user avatar
  • 129
3 votes
2 answers
498 views

Technical limitations of Turing machines due to the input and output encoding of values

Convention: Since I will be asking about some technicalities around Turing machines, it behooves to give a precise definition: say, here, “Turing machine” will stand for a $2$-symbol $1$-tape machine ...
Gro-Tsen's user avatar
  • 841
5 votes
0 answers
130 views

"Interesting" problems in $NLogTime \cap coNLogTime$

In terms of machine model, I'm interested in multitape Turing machines with random access to the input via a query tape. Criteria for "interesting" in this context: Not in $DLogTime$: "...
Jake's user avatar
  • 1,214
1 vote
0 answers
169 views

Decidability of the complexity of decision problems

This might be a question that is related to some of the existent questions on the topic in the title, but I still find some answers either not full, or the topic still slightly different (maybe due to ...
A. G's user avatar
  • 111
2 votes
0 answers
70 views

Resource bounded Kolmogorov complexity hardness on average over a non uniform distribution of inputs

$K^{poly}$, as well as other related problems such as $MCSP$, is believed to be hard on average [1, 2] when the input is sampled from a uniform distribution (since otherwise one way functions, pseudo-...
agemO's user avatar
  • 187
6 votes
1 answer
266 views

Fast algorithms for time bounded Kolmogorov complexity

For a universal Turing machine $U$, the time bounded Kolmogorov complexity of a string $x$ is silmilar to the usual Kolmogorov complexity but limited to programs $p$ running in time at most $t(|x|)$: $...
agemO's user avatar
  • 187
1 vote
1 answer
153 views

A contradiction in the realm of quantum digital and analog computation

It is a well known result that the circuit model of Quantum Computing (QC) is equivalent to the adiabatic model. Furthermore, the former is nothing more than a "slightly" more powerful ...
Marion's user avatar
  • 183
0 votes
0 answers
68 views

What is the meaning of the additive epsilon term in the definition of a time constructible function?

There is a well-known theorem that states that a function $f$ is time constructible if and only if $f$ can be computed in time $O(f)$. But this theorem comes with some conditions: $f$ must be a ...
user70015's user avatar
3 votes
2 answers
143 views

What is formal definition of non-deterministic algorithm in context of primitive/general recursion?

I want to understand general method for formally defining non-deterministic algorithm. But all formal definitions I see are related to FSM/Turing-machines. What is the reference for non-deterministic ...
uhbif19's user avatar
  • 315
7 votes
0 answers
188 views

Baker–Gill–Solovay Theorem: why $2^n/10$ steps?

Context I'm teaching an introductory complexity theory course right now and although I work in adjacent areas, I'm not an expert on complexity theory myself, so I'm still in the process of working ...
Manuel Eberl's user avatar
6 votes
0 answers
89 views

Time hierarchy for one-tape Turing machines

The time hierarchy for multitape Turing machines is tight (see [1]): if $f(n)=o(g(n))$ and $f,g$ are well-behaved, then $\textrm{DTIME}(f(n))\subsetneq \textrm{DTIME}(g(n))$. However, for one-tape ...
QMath's user avatar
  • 303
1 vote
1 answer
70 views

Probabilistic Turing machine of possibly correlated choices

A probabilistic Turing machine uses independent choices, as said in Wikipedia. At each step, the Turing machine probabilistically applies either the transition function $\delta_1$ or the transition ...
namasikanam's user avatar
2 votes
1 answer
119 views

Time complexity of computing homomorphic image

The class of regular languages $\textrm{REG}$ is closed under inverse homomorphisms. The class $\textrm{TIME}(n^k)$ of languages solvable by a one-tape TM is also closed under inverse homomorphisms ...
QMath's user avatar
  • 303
4 votes
1 answer
246 views

Halting problem proofs that do not utilise self-reference or diagonalization

Are there any proofs of the Halting problem that do not involve any self-reference, and diagonalization (or any diagonal argument) whatsoever? All the duplicate questions I have come across end up ...
Alan Whitteaker's user avatar
2 votes
1 answer
232 views

Examples for Real-time vs Linear time

A real-time Turing machine (with multiple tapes) runs in linear time. It is known [1] that there are languages recognizable in linear time by a multitape Turing machine but not recognizable in real-...
QMath's user avatar
  • 303
2 votes
3 answers
286 views

Turing Machines and Logic

It is well known that Monadic Second Order Logic (over words) and finite automata can express the same set of languages. Is there a logic over words (perhaps a nth order logic) such that it and turing ...
whoisit's user avatar
  • 135
5 votes
2 answers
186 views

Lower bound for sorting without using a decision tree model

Can we prove the lower bound for the sorting problem just by Turing machine model? It seems that available proof of sorting is based on the assumption that the algorithm only uses comparison so we can ...
Hao Huang's user avatar
0 votes
0 answers
147 views

On the use of Turing machines for computational complexity

Almost always in the study of computational complexity, the Turing machine is used as a model. On the other hand, the untyped lambda calculus is in a sense "simpler" than any Turing machine: ...
Wasabi Kurosawa's user avatar
0 votes
0 answers
41 views

Computability for universal quantum turing machines

I would like to ask if anyone has any ideas about what a universal quantum turing machine (UQTM) can do as supposed to a classical universal turing machine (UTM) (i.e. quantum computer vs classical ...
Shane Gervais's user avatar
2 votes
1 answer
135 views

Equivalence of a physical computer and Turing machine

In several talks and lectures, I've heard people saying that a physical computer is just a Turing machine but I'm unable to justify this analogy. My apprehension is the following: Without loss of ...
Akshay Bansal's user avatar
0 votes
1 answer
70 views

Trying to make sense of the operations in a particular Random Access Machine (RAM)

[I couldn't find the right tag for this post] Following is the description of some random access machine We use the algorithmic model of the random access machine, sometimes ab- breviated to RAM. It ...
roi_saumon's user avatar
2 votes
0 answers
121 views

Computing real numbers with Turing Machines

Consider the following decision problem: Given a two integers $n$ and $k$, decide whether $k=\lfloor n\pi\rfloor$ Question: Is this problem known to be in $P$? Although this may look like a stupid ...
Mathieu Mari's user avatar
5 votes
2 answers
151 views

Time/space lower bounds on Majority (in the multitape TM model)

MAJORITY is the language of bitstrings where more than half of the bits are 1s. I'm interested in lower bounds in the multitape TM model. This can be solved in $DTISP(O(n), O(\log(n))$ with a naive ...
Jake's user avatar
  • 1,214
1 vote
1 answer
119 views

Clarification sought re Li & Vitanyi's Proof of Godel Incompleteness in Formal System F

(Cross-posted from Computer Science due to lack of response after 1 week) From An Introduction to Kolmogorov Complexity and Its Applications, Li & Vitany, 4th Ed. Example 1.1.1. As you might guess,...
Julian Moore's user avatar
1 vote
0 answers
60 views

Generalization of computability to continuous for loops? [closed]

A computable function, formulated in the sense of mu recursion, can compute a for or do loop over some (possibly infinite) integer range. I was wondering if a suitable generalization exists that ...
Abhimanyu Pallavi Sudhir's user avatar
-2 votes
1 answer
133 views

Can a Turing machine quickly move to any position of a large string?

I hope this question is not too basic and I am not missing something dumb. But suppose we simulated a Turing machine on a long string $s$, where $|s| = 10^{100}$ for example. Then if we wanted to ...
user918212's user avatar
1 vote
0 answers
156 views

Relation between BSS and Turing models

$P_\mathbb R$ is the set of languages decidable in polynomial time over the real $BSS$ machine defined in https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine. Let $0-1-P_\mathbb R=\{...
Turbo's user avatar
  • 12.9k
0 votes
1 answer
222 views

Understanding the construction of an uncomputable function

The following is from Arora and Barak's "Computational Complexity." I think one does not have to read the second paragraph of the proof to answer this question. Theorem 1.10 There exists a ...
zxcv's user avatar
  • 109
-8 votes
1 answer
397 views

Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state? [closed]

...
polcott's user avatar
  • 59
3 votes
0 answers
123 views

Detailed proof of Theorem 2.1 in Papadimitrou book (Multitape TM to SingleTape TM)

I want to know if anybody knows a detailed proof of Theorem 2.1 of Papadimitrou's book Computational Complexity. The theorem states "Given any $k$-string Turing machine $M$ operating within time $...
arbolverde's user avatar
8 votes
1 answer
172 views

Q: Trusting program output from an untrusted machine

Let's suppose that we create a program P, that given input I, generates output O. We then want to run this program on an untrusted computer C that may either want to tamper with the program (run P' ...
DarthShader's user avatar
1 vote
0 answers
113 views

Does any physical process constitute a "computation"? [closed]

I am trying to sharpen the convex hull of what seems like a (surprisingly) stubborn concept to enclose based on answers here, as well as conversations with others, around the nature of what actually ...
dnnct's user avatar
  • 27
0 votes
1 answer
128 views

Complexity for universal Counter Machine with {0,1}-valued registers

Consider a universal $\{0,1\}$-$k$-counter machine where each of the $k$ registers has a value in $\{0,1\}$ (as opposed to any non-negative integer in the usual formulation), and there are states $q_1,...
RRRR's user avatar
  • 1
5 votes
1 answer
915 views

Is coRE closed under concatenation?

I know that RE is closed under union, intersection, and concatenation (but not complement). It is likewise easy to show that coRE is closed under union and intersection (but not complement). What ...
Aryeh's user avatar
  • 10.6k
0 votes
0 answers
172 views

Is BigInteger-based Brainfuck Turing Complete?

All of the proofs of Turing-Completeness I've found for Brainfuck rely on its cells being fixed-width integers that wrap around upon over/underflow. The "parent language" P'' on which ...
user513093's user avatar
2 votes
0 answers
111 views

Halting behavior of a randomly selected Turing machine?

Let $TM(k,2)$ be the set of Turing machines with $k$-states and $2$ symbols. Let $h(k)$ be the number of machines in $TM(k,2)$ that halt when run on the blank input. Is $\lim_{k \to \infty} \frac{h(k)...
user101010's user avatar
7 votes
1 answer
369 views

Is there a concept of "Lego complete"? If not, does it make sense to develop one?

We know the concept of Turing Completeness. These days when I play lego with my kids. I realised that Lego is kinda like programming language: we can build a lot of things with a fairly small set of ...
user152503's user avatar
3 votes
1 answer
307 views

Formalization of simulation for Turing machines

Right now I am trying to understand the concept of simulation in theoretical computer science, focussing on Universal Turing machines. All textbooks that I looked into only explain examples. They ...
QuantumAI's user avatar
  • 147
14 votes
1 answer
1k views

Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

Question: Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines? Background: I recently stumbled upon the ...
Michael Wehar's user avatar
7 votes
1 answer
459 views

How fast is an equivalent 2-tape TM compared to a $O(n^2)$ 1-tape TM?

In $O(n^2)$ steps, a 1-tape TM can simulate a 2-tape TM that runs for $O(n)$ steps. How fast is an equivalent 2-tape TM known to run compared to a $O(n^2)$ time, 1-tape TM? "Open question" ...
Zachary Vance's user avatar
4 votes
2 answers
276 views

Dependence of decidability on the encoding of Turing machines

Let $f : \{0, 1\}^* \to \{0, 1\}^*$ be a computable function. Given any encoding $\left<M\right>$ of Turing machines over binary (i.e., a function from the set of Turing machines to the set of ...
RandomStudent's user avatar
1 vote
1 answer
316 views

How come Wikipedia says that Random Turing Machines can provide uncomputable output?

Wikipedia article mentioned : Hypercomputation The third paragraph starts off with: Technically, the output of a random Turing machine is uncomputable; however, most hypercomputing literature focuses ...
Novicegrammer's user avatar

1
2 3 4 5