Questions tagged [turing-machines]

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

Filter by
Sorted by
Tagged with
2 votes
2 answers
428 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
  • 619
5 votes
0 answers
118 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,204
0 votes
0 answers
165 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
  • 101
2 votes
0 answers
69 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
228 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
140 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
63 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
121 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
  • 295
7 votes
0 answers
171 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
82 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
0 votes
0 answers
45 views

Turing machine with ordered set of states

Consider a computing model with two tapes: one of them contains data and the other contains the set of instructions: what to do if the machine observes symbol $a_i$: move the first tape left/right/...
jokersobak's user avatar
1 vote
1 answer
65 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
115 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
216 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
211 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
1 vote
3 answers
255 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
  • 125
5 votes
2 answers
178 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
138 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
38 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
129 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
66 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
113 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
143 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,204
1 vote
1 answer
106 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
127 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
147 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.8k
0 votes
1 answer
207 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
381 views

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

By making a slight refinement to the halt status criterion measure that remains consistent with the original a halt decider may be defined that correctly determines the halt status of the conventional ...
polcott's user avatar
  • 45
3 votes
0 answers
121 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
164 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
123 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
847 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.3k
0 votes
0 answers
162 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
109 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
337 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
278 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
406 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
268 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
283 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 vote
1 answer
175 views

What kind of computational model is the brain? [duplicate]

I was wondering what kind of computational model is the human brain (as it seems superior to a Turing machine). Another thing that should be a separate question, What would be a perfect computer model ...
Aether's user avatar
  • 133
0 votes
0 answers
115 views

Can you diagnolize without mentioning simulation?

Are there any known diagonalization proofs, of a language not being in some complexity class, which do not explicitly mention simulation? The standard diagnolization argument goes: here is a list of ...
mark's user avatar
  • 39
1 vote
0 answers
95 views

Given a program specification, S, what can be said about the size and efficiency of programs that exactly satsify S, with respect to the size of S?

Suppose we are given a program specification, $S$, and we want to reason about programs $P$ that satisfy $S$. One might like to think that if the specification is 'simple', the the program should be '...
user10108's user avatar
-3 votes
1 answer
76 views

Show that membership in L is undecidable [closed]

Let L ⸦ {0, 1}* be the language {(M, x) | Turing Machine M on input x enters every state of M at least once}. How can I show that membership in L is undecidable?
Kwaku's user avatar
  • 5
6 votes
1 answer
243 views

Is $L \subset 1NL$ when $L \neq NL$?

A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which ...
Frank Vega's user avatar
3 votes
2 answers
181 views

$DTIME_1(o(n^2))\setminus$ REGULAR

Maybe this is well-known, but I couldn't find any example of a non-regular lanugage that is decidable on a single-tape Turing machine in subquadratic time. Help! Related paper: On the structure of ...
domotorp's user avatar
  • 13.9k
1 vote
1 answer
318 views

Prime factorisation of decidable problems

Disclaimer: I am not a theoretical computer scientist. The set of decidable problems $\mathbb{D}$ is countable so $\lvert \mathbb{D} \rvert = \lvert \mathbb{N} \rvert$ and this led me to the ...
Aidan Rocke's user avatar
2 votes
0 answers
78 views

Can $\mathsf{P}^{\#\mathsf{P}}$ be described in terms of a non-deterministic (alternating) Turing machine?

Can the $\mathsf{P}^{\#\mathsf{P}}$ (= $\mathsf{P}^{\mathsf{PP}}$) class be described in terms of a non-deterministic Turing machine (in particular, an alternating Turing machine)? And would a $\...
Sanchayan Dutta's user avatar

1
2 3 4 5