Questions tagged [turing-machines]
The Turing machine is a fundamental model of computation, especially in theoretical work.
219
questions
1
vote
0
answers
47
views
Question About Turing Machine Computability [closed]
If p is a Turing machine then L(p) = {x | p(x) = yes}.
Let A = {p | p is a Turing machine and L(p) is a finite set}.
Is A computable? Justify your answer.
So I'm trying to figure out how to solve ...
- 11
4
votes
0
answers
95
views
Libraries for programming automata and Turing machines
What are the most useful libraries around for coding related to automata and Turing machines?
By useful I mean the number of functions and algorithms supported by it.
5
votes
0
answers
606
views
Games on Turing machines that are AH-hard
I'm interested in proving that finding optimal play in a particular two-player game is harder than the arithmetic hierarchy. I suspect this to be true, because even carrying out a deterministic end-...
- 1,046
0
votes
1
answer
695
views
What is the practical importance of making or using a Turing complete language? [closed]
I get what a Turing machine is and what language is a Turing-complete language but when someone introduces me to a new programming language (like Solidity) and says it is Turing complete, what am I ...
- 19
3
votes
2
answers
902
views
For a specific unbounded Turing machine, is its Halting problem undecidable?
The question is on the title.
To make it clearer, I state some facts. We all know that the Halting problem with input is undecidable. It leads to, given a specific input (e.g. empty string), the ...
- 169
12
votes
1
answer
1k
views
How good can a halting detector be?
Is there a Turing Machine that can decide whether almost all other Turing Machines halt?
Suppose we have some enumeration $\mathbb{N} \rightarrow \{M_i\}$ of Turing machines, and some notion of "...
- 223
1
vote
1
answer
340
views
What is the VC dimension of Turing machines with specified maximum size?
Note by "maximum size" in the question I'm referring to the size of the Turing machine's state machine.
I chose Turing machines in the question to make the question concrete, but I'm also more ...
- 105
5
votes
1
answer
197
views
Turing machines over a structure
I have heard of models of computation where you have a Turing machine, but instead of symbols over a finite alphabet you have elements from some tau-structure, and write instructions are replaced with ...
- 633
4
votes
2
answers
1k
views
Enumerating decidable languages
[The assumption in this question is wrong. It is possible to enumerate exactly the decidable languages with semideciders.]
Lets say we have a TM $M_E$ enumerator that writes out codes of TM's on a ...
- 153
1
vote
2
answers
523
views
What is the time complexity of base conversion on a multi-tape Turing machine?
Base conversion is the problem of converting an integer between representations in two fixed bases. Without loss of generality consider the case of relatively prime bases. I think it's easier to ...
- 550
30
votes
1
answer
1k
views
Functions that are Not Efficiently Computable but Learnable
We know that (see, e.g., Theorems 1 and 3 of [1]), roughly speaking, under suitable conditions, functions that can be efficiently computed by Turing machine in polynomial time ("efficiently computable"...
- 812
4
votes
0
answers
294
views
How fast can we sort a list if we know how it was written?
Let $G$ be a linear time (deterministic) turing machine that takes positive integers $n$ in unary to lists of length $n.$ For any fixed such $G$, define sparse-sort(G,n) as the problem of sorting the ...
- 141
-1
votes
2
answers
262
views
Why bother with deterministic Turing machines when nondeterministic Turing machines consume less space and time? [closed]
I have a question on a part from the wikipedia page on Savitch's theorem: https://en.wikipedia.org/wiki/Savitch%27s_theorem
The part in question is the following:
[...], if a nondeterministic ...
- 275
3
votes
0
answers
222
views
Is there any known strategy that avoids circuits and that respects believed separations to prove $P$ is not $NP$?
Vinay Deolalikar's approach tried to randomness is not strong enough, Blum's proof tried to show $P/poly$ is not strong enough, Mulmuley's and Smale's approach (while not enough to show $P\neq NP$) ...
- 12.6k
12
votes
1
answer
619
views
Compressing information about the halting problem for oracle Turing machines
The halting problem is well-known to be uncomputable. However, it is possible to exponentially "compress" information about the halting problem, so that decompressing it is computable.
More precisely,...
- 221
6
votes
0
answers
179
views
Small universal monotone Turing machines
This paper surveys small universal Turing machines. What are some examples of small universal monotone Turing machines, as described by Schmidhuber? Which of these are efficient (polynomial time) ...
- 642
1
vote
0
answers
86
views
Question on Turings Dissertation *Systems of Logic based on Ordinals*, Axiomatic Properties [closed]
I have a question on Alan Turing's Dissertation Systems of Logic Based on Ordinals, a scanned copy you can find here, or rewritten in LaTeX here, and also a copy of the published version here (but in ...
- 1,977
9
votes
3
answers
3k
views
Class of languages recognizable by single-tape 3-state TMs
I have for a while been curious about Turing Machines with exactly one tape and exactly 3 states (namely the start state $q_0$, the accept state $q_{accept}$, and the reject state $q_{reject}$). Note ...
- 2,758
12
votes
1
answer
496
views
Time Hierarchies in DSPACE(O(s(n)))
The time hierarchy theorem states that turing machines can solve more problems if they have (enough) more time.
Does it hold in some way if the space is limited asymptotically?
How does $\textrm{DTISP}...
- 59
9
votes
0
answers
369
views
Is there a Turing complete planetary system?
Seemingly simple things have turned out to be capable of computation - Conway's Game of Life, Wolfram's Rule 110, etc.
Has anyone devised a Turing complete system using suns, planets, moons, sub-...
- 199
1
vote
0
answers
187
views
An alternative model of a probabilistic Turing machine [closed]
A probabilistic Turing machine operates with an additional tape of random bits, and its output is a random variable with some distribution over the random bits. Is it also useful to talk about the ...
- 111
2
votes
0
answers
89
views
Is there a DCSL that cannot be recognized in O(n^2) steps by a deterministic LBA?
Is there a context sensitive language $L$ so that $L$ cannot be recognized by a deterministic linear bounded turing machine in $O(n^2)$ steps, but still can be recognized by a deterministic LBA?
The ...
- 59
1
vote
0
answers
104
views
Convenient forms of Turing machines
Let us suppose that I have defined a new convenient form of the Turing machine for processing of some specific sort of commonly used structures.
This form of TM contains some specific features ...
- 635
1
vote
1
answer
570
views
A question of relationships between #P and PSPACE [closed]
Let us assume there is some machine X that converts boolean formula to following form in polynomial time:
$$\Phi(x_1, x_2 .. x_m) = r_1(x_{i_1}, x_{j_1}, x_{k_1}) \land r_2(x_{i_2}, x_{j_2}, x_{k_2}) ...
- 207
1
vote
2
answers
2k
views
Is iszero of the untyped lambda calculus sound and complete? [closed]
I am using the following definitions in the notation of Haskell. In case it matters, I would like to use only the $\alpha,\beta,\eta$ reductions rather than the Haskell evaluation rules.
...
- 173
0
votes
1
answer
164
views
Enumerator for the language w#w^R? [closed]
I'm trying to build a Turing machine diagram for the language w#w^R, where w^R is the reverse of w, and w is a word made up of 0's and 1's. I'm trying to think of an algorithm but I can't think of ...
- 19
2
votes
1
answer
92
views
Characterisation of computability of partial functions from infinite words into finite words by functions with prefix-free domain
The following is taken from K. Weihrauch, Computable Analysis, page 21. The notation $f : \subseteq A \to B$ means a partial function. By $\Sigma^{\omega}$ and $\Sigma^{\ast}$ we denote the set of ...
- 1,977
2
votes
5
answers
426
views
A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise
Consider the following definition:
A number $x \in \mathbb R$ is computable, if there exists a (one-tape) Turing machine which (running infinitely long) writes the binary expansion of $x$ onto its ...
- 1,977
19
votes
3
answers
2k
views
"The" category of Turing machines?
Disclaimer: I know very little about complexity theory.
I'm sorry but there is really no way to ask this question without being (terribly) concise:
What should be the morphisms in "the" category ...
- 301
15
votes
2
answers
473
views
(How) Could we discover/analyze NP problems in the absence of the Turing model of computation?
From a purely abstract math/computational reasoning point of view, (how) could one even discover or reason about problems like 3-SAT, Subset Sum, Traveling Salesman etc.,? Would we be even able to ...
- 5,225
4
votes
0
answers
107
views
Why primitive rotation is $53.13^\circ$ in the quantum Turing machine used by Vitanyi for Quantum Kolmogrov Complexity?
Right now I am going through Quantum Kolmogorov Complexity Based on Classical Descriptions by Vitanyi.
In the introduction, the author assumed the primitive rotation $\theta = 53.13^\circ$ to have ...
- 331
7
votes
3
answers
584
views
Where does the modern canonical version of the Turing machine come from?
Turing's original 1936 description of his a-machine differs in several respects from the Turing machine I studied at university, leading me to questions:
The Turing machine I learned about was ...
- 179
0
votes
0
answers
157
views
Questions about the definition of the Quantum Turing Machine
I am trying to have a better understanding of the definition of the Quantum Turing Machine.
My questions:
If the output of a quantum program is the eigenvalue of the ground state of a Hamiltonian ...
- 331
-1
votes
1
answer
547
views
Where can I find a Turing machine evaluating arithmetic expressions? [closed]
Is there a Turing machine that can evaluate arithmetic operations with brackets containing +, -, and ...
- 109
-2
votes
1
answer
126
views
Are there any known problems that require potential nontermination to solve? [closed]
Apart from problems that specifically have to do with Turing machines, like "Simulate a Turing Machine with the given description", are there any problems that require Turing-complete potentially ...
- 131
0
votes
1
answer
198
views
A metric space on Turing machines
Let $L$ be a decidable language. Let $X^L$ be the set of deterministic Turing machines which decide $L$. Define two machines $A,B\in X^L$ to be time-equivalent if $t_A(w) = t_B(w)$ for all $w \in \...
user35803
-1
votes
1
answer
651
views
Understanding between lambda-calculus and other abstract machines (like Turing machine and Markov algorithm)
If we look on abstract machines we could noticed analogue with modern computers (of course). What I mean? I mean this points:
1. Model of implementer (In Turing machine it is description of head, ...
- 25
3
votes
1
answer
557
views
Can all mathematical operations be encoded with a Turing Complete language? [closed]
In High School Computing I was taught the Structured Program Theorem - that you could implement any mathematical operation using:
Sequence
Selection
Iteration
After completing a Computer Science ...
- 2,541
4
votes
2
answers
248
views
Characterisation of P in terms of register machines
It is a well-known result that Turing machines and random access machines (RAMs) can simulate each other with a polynomial slowdown.
It is relatively straightforward to prove that indirect addressing ...
35
votes
3
answers
3k
views
Turing Machine restrictions that render halting decidable
If one restricts Turing Machines to a finite tape (i.e., to use bounded space $S$),
then the halting problem is decidable, essentially because after a number of steps (which can be calculated from the ...
- 3,703
0
votes
2
answers
934
views
Halting problem for finite tape TM [closed]
If we have a primitive CPU/computer with small amount of registers and/or RAM, it is easy to check if the program will loop endlessly: just write down all registers/RAM cells states at each state and ...
45
votes
10
answers
16k
views
Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?
Real computers have limited memory and only a finite number of states.
So they are essentially finite automata.
Why do theoretical computer scientists use the Turing machines
(and other equivalent ...
- 617
3
votes
1
answer
169
views
What is the simplest universal unidimensional interaction net system?
The Interaction Combinators are possibly the simplest multidimensional system of interaction nets that is Turing-complete. What about interaction nets with only 2 ports - 1 principal, 1 auxiliary? ...
- 3,035
2
votes
1
answer
630
views
Langton's ant questions
I'm a mathematician currently working on the Langton's ant conjecture, just for fun. I have some result but I don't know if they are meaningless.
So that is why I'm asking.
1)
Is there a mathematical ...
- 131
1
vote
1
answer
1k
views
Multi Head universal Turing machine
It is common knowledge that a universal Turing machine can simulate any Turing machine with logarithmic overhead. Is it possible to make this overhead constant by constructing an analogous "Universal" ...
- 121
9
votes
1
answer
215
views
Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?
Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?
By a nondeterministic linear bounded automaton (nLBA) I mean a single-tape nondeterministic Turing machine ...
- 455
3
votes
1
answer
185
views
Does Wikipedia assume a solution to the halting problem in their description of universal one way functions?
(As for the question in the title: the answer must be no, but then I don't understand what is intended.)
The Wikipedia page on one way functions states:
Goldreich gives one construction of a ...
- 269
0
votes
2
answers
310
views
Are there any open problems concerning decidability? [duplicate]
I am learning computability theory. I am just interested to know some famous problems (Formally languages) whose decidability is in question.
- 119
19
votes
2
answers
2k
views
Is there a non-deterministic linear time algorithm for CNF-SAT?
The decision problem CNF-SAT can be described as follows:
Input: A boolean formula $\phi$ in conjunctive normal form.
Question: Does there exist a variable assignment that satisfies $\phi$?
I'm ...
- 5,025
0
votes
3
answers
581
views
Fastest Turing Machine
Recently I have been reading about Kolmogorov Complexity.
As such I started thinking about the "fastest turing machine".
In particular I am not interested in finding such a machine, I am only ...
user35803