Questions tagged [turing-machines]
The Turing machine is a fundamental model of computation, especially in theoretical work.
232
questions
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 ...
- 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$: "...
- 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 ...
- 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-...
- 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|)$:
$...
- 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 ...
- 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 ...
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 ...
- 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 ...
- 273
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 ...
- 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/...
- 117
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 ...
- 113
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 ...
- 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 ...
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-...
- 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 ...
- 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 ...
- 51
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: ...
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 ...
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 ...
- 123
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 ...
- 103
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 ...
- 475
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 ...
- 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,...
- 113
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 ...
-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 ...
- 99
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=\{...
- 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 ...
- 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 ...
- 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 $...
- 51
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' ...
- 183
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 ...
- 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,...
- 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 ...
- 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 ...
- 119
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)...
- 251
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 ...
- 171
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 ...
- 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 ...
- 5,127
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" ...
- 353
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 ...
- 151
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 ...
- 173
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 ...
- 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 ...
- 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 '...
- 41
-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?
- 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 ...
- 119
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 ...
- 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 ...
- 311
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 $\...
- 307