Questions tagged [turing-machines]
The Turing machine is a fundamental model of computation, especially in theoretical work.
258 questions
2
votes
1
answer
66
views
Alternating Polynomial Space with Linear Number of Alternations
Consider alternating TMs with polynomial space and at a linear number of alternations. Is the halting problem for this class EXPTIME-complete, or does the linear alternation bound place it somewhere ...
- 1,514
2
votes
0
answers
93
views
Nondeterministic Turing machine and group theory
A Turing machine can be seen as a configuration transition $T$ which brings a configuration $x$ into a configuration $y$, such that the configuration after $n$ steps, starting from $x$, is $T^n(x)$.
...
- 123
0
votes
0
answers
46
views
Complexity of sorting with block simulation
In the paper of Valiant and Hopcroft et al "On Time versus space and related problems" I'm trying to understand the theorem 2 in section 3 "On the complexity of sorting". I don't ...
1
vote
0
answers
85
views
Fastest time bound for the general circuit value problem on a parallel machine
I'm trying to figure out what's the fastest time bound that's been discovered for the general circuit value problem on a PRAM (parallel machine). Concurrent Read/Exclusive Write (CREW) or Concurrent ...
3
votes
3
answers
378
views
Advanced texts in theoretical computer science
I'm finishing learning a course in Theoretical Computer Science based in Sipser's textbook. I find it very basic and quite useful for the introduction of the topic, but I would like to continue the ...
- 131
3
votes
2
answers
609
views
Turing machine halts on any input but not provably total
Is in any $\Sigma_1$-sound recursively enumerable first order theory $T$ extending arithmetic, there is a Turing machine $M$ such that for all input $n$, $T$ proves that $M$ halts on $n$, while ...
- 141
0
votes
0
answers
47
views
Resource-Bounded Measure and Non-Determinism
How can we extend classical notions of martingales and resource-bounded measure theory to non-deterministic Turing machine models? Could such a formulation shed more light on derandomization ...
- 31
0
votes
1
answer
186
views
Is there a recursive-enumerable list of Turing Machines which accept a recursive language each such that the list covers all recursive languages?
This is an excersize problem from Kozen:
Show that there exists an recursive-enumerable (r.e.) list of Turing machines such that every machine on the list accepts a recursive set and every recursive ...
6
votes
1
answer
214
views
Are $\beta$-reductions "faster" than Turing Machine steps?
Let's define a "lambda machine" as a machine that, at every step, performs (in normal order) a $\beta$-reduction on a lambda calculus expression. It terminates when no more reductions can be ...
- 163
0
votes
0
answers
127
views
Why is Bennett's simulation reversible?
A reversible Turing machine ($\mathsf{RTM}$) is a Turing machine ($\mathsf{TM}$) whose transition function is a bijection, so that each instantaneous description ($\mathtt{ID}$) has at most one ...
2
votes
0
answers
118
views
Definitions of space-bounded oracle Turing machines
I have a question regarding the definition of the query model for space-bounded oracle TMs.
There are various query models (see, e.g., [1]). Among them, two prominent ones are:
bounded query model, ...
- 201
2
votes
1
answer
554
views
Generalization of Büchi-Elgot-Trakhtenbrot theorem
There is a well known correspondence between automata and languages (e.g. Chomsky heirarchy).
The Büchi-Elgot-Trakhtenbrot (BET) theorem characterizes regular languages as formalizable in monadic ...
0
votes
0
answers
70
views
Problem classes based on additional memory
Is there a classification of problems based on
how much additional memory (other than input) they would need?
For context: assume we have a multi-tape Turing machine $M$,
with a bounded input tape and ...
- 1
10
votes
2
answers
440
views
Halting problem with minimal Turing Machine as promised input
Consider the following Turing Machine A.
Input: Turing Machine M that recognizes some language L(M)
Output:
If M is minimal (i.e. its length is minimum among Turing Machines that recognize the same ...
- 109
1
vote
0
answers
116
views
Smallest 2-symbols Turing machine that can decide primality using unary encoding
I am interested in Turing machines that can decide primality using only two symbols and, hence, unary encoding for the input. Currently I have a solution that has 29 useful states (not counting the ...
- 171