Questions tagged [turing-machines]

Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.

195 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10
votes
0answers
752 views

Universal Turing Machine simulation with bounded time overhead

Is it possible to design a Universal Turing Machine in which the simulation time of a given Turing Machine $M$ is bounded by a factor of $\mathcal{O}(\log|\Gamma|+\log|Q|)$ of the original running-...
8
votes
0answers
822 views

Complexity of Sorting Integers on a Multitape Turing Machine

How expensive is sorting integers on a Multitape Turing Machine? Well known sorting algorithms, like quicksort, tend to rely on jumping / indirect-access being cheap. But MTMs have no indirect access.....
6
votes
0answers
30 views

Unbounded-time programs in lambda calculus?

The Turing machine model has been extended to “infinitary turing machines”, which are Turing machines that can perform a countably and uncountably infinite amount of computations in finite time. Is ...
6
votes
0answers
67 views

Can all computational complexity results be expressed in terms of programming languages?

Computational complexity results are often explained in intuitive terms as statements about the possible efficiencies of algorithms to solve certain classes of problems. However, on a more formal ...
6
votes
0answers
50 views

What is the minimum acceleration of a macro machine?

In the context of Turing machines, consider a $k$-sized macro machine (k-MM) which operates on groups of $k$ symbols at once. This is a common optimization in the search for Busy Beavers, explained e....
5
votes
0answers
769 views

Understanding Levin's Universal Search

I am having troubles understanding Levin's universal search method. In Scholarpedia, http://www.scholarpedia.org/article/Universal_search, it is claimed that “If there exists a program $p$, of length $...
5
votes
0answers
696 views

Compiler that compiles to a Turing machine?

I am interested in finding/writing a compiler that compiles a program written in a simple source language to a Turing machine (instead of assembly). Does anyone know if there is a good approach for ...
5
votes
0answers
170 views

Difficulty in the halting problem for a simple Turing machine with standard enumerations of programs and of initial tape configurations

Preparations Consider a Turing machine with just one head and one tape (on which the head may move left, move right, or remain stationary), and with just two symbols ("blank" and "non-blank"). The ...
4
votes
0answers
91 views

How to model reversible interactive programs

Reversible programs with finite execution steps are well studied. For example, a Turing machine whose transitions are reversible and halts can be executed backwards consuming its tape in the reverse ...
4
votes
0answers
103 views

Is a reduced Wang B-machine Turing-complete?

A Wang B-machine has only 4 instructions: right: Move tape head right left: Move tape head left ...
4
votes
0answers
971 views

Oblivious Universal Turing Machine in O(T log(T)) time

I'm currently reading Computational Complexity: A Modern Approach. In this book, they give a proof of a universal Turing machine $U$ such that if $M(x)$ runs in $T$ steps, then $U(\lfloor M \rfloor, x)...
4
votes
3answers
412 views

Decidability of the TM's computing a non-empty subset of total functions

I have this HW problem: Let $F$ be the set of computable total functions, and let $\emptyset\subsetneq S\subseteq F$. Denote $$L_S=\{ \langle M \rangle | M \text{ is a TM that computes a function ...
4
votes
1answer
654 views

How to simulate a bidirectional TM on a regular one with time factor four?

In Computational Complexity A Modern Approach, one claim says that if $f$ is computable in time $T(n)$ by a bidirectional TM $M$, then it is computable in time $4T(n)$ by a unidirectional TM $\tilde{M}...
4
votes
0answers
2k views

Prove that turing machines and the lambda calculus are equivalent

It is known that a turing machine and the lambda calculus are equivalent in power. I now want to try to prove this myself. I think proving that the lambda calculus is at least as powerful as a turing ...
4
votes
1answer
124 views

Proving a certain superset the halting language is not recursive

Let $\Sigma =\{ 0, 1\}$. Let $val:\Sigma^* \rightarrow \mathbb{N}$ be a function that given a string returns its decimal value, and $L_{halt} = \{\langle M\rangle \langle w\rangle \mid M $ halts on $w ...
4
votes
1answer
138 views

Advances in recent time in Von-neumann self replication idea

I have read about Von-neumann self replication from Theory of Self-reproducing automata, which are lecture notes reconstructed from lectures in book of the same name. Theory of Self-reproducing ...
3
votes
1answer
103 views

$TSAT$ is $NP$-complete

In "Computational Complexity" by Arora and Barak they state that the following is $NP$-complete: $\{ \langle \alpha, x, 1^n , 1^t \rangle : \exists u \in \{0,1\}^n \text{ s.t. } M_{\alpha} \text{ ...
3
votes
0answers
101 views

Limits on the time of computation for a UTM simulating a TM

According to source page 20, theorem 1.9, it states that there is a universal Turing machine that can simulate any Turing machine with a time overhead of $O(\log n)$. Can a universal Turing machine ...
3
votes
0answers
71 views

Direct reduction $L_{REG}\le_m L_{CFG}$

Both $L_{REG}=\{ \langle M \rangle : L(M)\text{ is regular}\}$ and $L_{CFG}=\{ \langle M \rangle : L(M)\text{ is context-free}\}$ are $\le_m$-complete for $\Sigma_3^0$ in the arithmetic hierarchy. ...
3
votes
0answers
176 views

Are Turing machines with a limited but exponential tape decidable?

The Halting problem for Turing machines which work on a tape of at most $k$ cells can be solved: There is a limited number of distinct configurations available, providing an upper bound of steps ...
3
votes
0answers
83 views

Why does using an encoding trick like Gödel numbers make a register machine universal?

Here the author describes the Random Access Stored Program machine and the problem of indirect addressing. The author states: But this does not solve the problem (unless one resorts to Gödel ...
3
votes
0answers
163 views

A complete catalog of 2-state Turing machines?

For educational purposes, I'm about to start a research project that involves creating a complete database documenting and classifying all 2-state, 2-symbol Turing machines, according to a ...
3
votes
0answers
161 views

Time Complexity of Simulating CA with TM

This question is a follow up to the question: Proving Equivalence of 1-dimensional Cellular Automaton and Turing Machines. To simulate a CA with a TM, I used a construction which placed a marker on ...
2
votes
0answers
34 views

A push-down automaton with two stacks which is equivalent to a linear-bounded automaton

It is known that a PDA with two stacks is equivalent to a TM. On the other hand a PDA with one stack is capable to recognise only context-free languages. Hence there is a kind of a gap between the ...
2
votes
1answer
35 views

How To Show That B is Semi-Decidable Given A

I am preparing for my Computational Theory final and ran into this exact problem : B={ x | there exists a prefix of x that is in A}. Show that B is semi-decidable. In other words, you need to ...
2
votes
1answer
61 views

Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times

I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation"). Can I just use ...
2
votes
0answers
25 views

Is there a formal way of defining a Zeno Machine?

The idea of a Zeno machine is pretty interesting to me, but I can't seem to find a formal definition for how a Zeno machine would work. I can find a couple of definitions around but they are all ...
2
votes
0answers
718 views

Turing machine VS Push Down Automaton in CFL

I want to ask that between turing machine and pushdown automaton: which abstract machine can handle context-free language (CFL) in a more efficient way, and why? I know that a pushdown automaton can ...
2
votes
0answers
105 views

Equivalence between different Turing Machines and a definition of simulation

Im having some difficulty understanding how the following two concepts could be related. Equivalence between TMs as is commonly tought According to this site answer, to prove a standard TM model to ...
2
votes
0answers
37 views

Is the language $L$ of coded CFG's Turing decidable?

Consider the following language $L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$} Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
2
votes
0answers
30 views

Reference request: Algorithms on Turing Machines

Is there a good survey or some papers with algorithms in the Turing machine model? I know the paper STRING-MATCHING AND OTHER PRODUCTS contains Turing Machine version of KMP. Are there any other such ...
2
votes
0answers
167 views

Simulating a turing machine with DPDA with two stacks

In general, the idea for simulation a turingmachine using a PDA with two stacks, is to use one stack representing the already read input and the second stack representing the unread part of the input. ...
2
votes
0answers
97 views

Simulating QC using nondeterministic Turing machine

Is it more efficient to simulate Quantum Computer using a non-deterministic Turing machine? Would it be more efficient than simulation using a deterministic Turing machine or probabilistic Turing ...
2
votes
0answers
68 views

Assuming that $P \neq NP$, show that there exist sets $A$ and $B$ in $NP$ such that neither $A \leq _T^p B$ nor $B \leq _T^p A$

My question is as follows: Assuming that $P \neq NP$, show that there exist sets $A$ and $B$ in $NP$ such that neither $A \leq _T^p B$ nor $B \leq _T^p A$, where $A \leq _T^p B$ if there exists a ...
2
votes
0answers
42 views

Decidability/recognizability of languages with strings lacking alphabet characters

Suppose that $\Sigma = \{c_1, \dots, c_m\}$ is some finite alphabet and supposing $s \in \Sigma^*$, let $\mathcal{I}_j(s)$ denote the number of instances of character $c_j$ in $s$. Call a string $s$ ...
2
votes
0answers
1k views

How to build a TM state diagram for a given language

I came across following TM state diagram accepting language $\{a^nb^nc^n | n\geq 0\}$ After trying out some valid and invalid strings of various lengths, I was surprised how it is designed to accept ...
2
votes
0answers
94 views

Prove $\forall a>0.BPP[{a,a+\frac{1}{n}}]=BPP$

I need to prove that $\forall a>0.BPP[{a,a+\frac{1}{n}}]=BPP$ $BPP[a,b]$ definition: A language L is in BPP(a,b) if and ...
2
votes
0answers
321 views

Explaining TM notation in Lewis/Papadimitriou

I was working on some questions in the book "Elements Of The Theory Of Computation", by Lewis and Papadimitriou, and I need help with one question - question 4.1.8 (chapter 4): Give the full ...
2
votes
0answers
59 views

Uses of unary or sparse languages in other models

In the turing model we have the statements that if there is an unary or sparse language that is NP complete then P=NP and if there is a Turing reduction from an NP complete problem to an unary or ...
2
votes
0answers
67 views

Random Access Machine output

It is known that when a Random Access Machine halts the output on the registers is going to be $R_1,\ldots,R_{||R_0||}$ after going through its instruction set where $||R_0||$ denotes the length of ...
2
votes
0answers
64 views

Expressing classic automata in modern terms

This semester I was introduced to finite automata (FSM), then pushdown automata (PDA), and now the Turing machine (TM). Granted that there're many possible implementations of these abstractions (...
2
votes
0answers
306 views

Decidable non time constructible function

Can anyone help me find an example of a function $f:\mathbb{N}\rightarrow\mathbb{N}$ which satisfies $\forall n\in\mathbb{N}: f(n)\ge n$ and is decidable, i.e. there exists some Turing machine $M_f$ ...
2
votes
0answers
48 views

What are the fundamental principles/algorithms on the process of equation solving?

I have seen a lot of solvers that are capable of, for example, getting an equation such as x ^ 2 + x = 12 and finding x = [3, -4]. I know some of them are implemented by hardcoding special cases. For ...
2
votes
0answers
441 views

How to simulate a cellular automaton via a Turing machine

It is rather easy to see that every cellular automaton can be simulated by a Turing machine: We can simulate a cellular automaton with an appropriate C program and every C program can be simulated by ...
1
vote
0answers
53 views

Encoding any turing machine to one with 2 symbols

This is a repost from https://stackoverflow.com/questions/56990710/encoding-any-turing-machine-to-one-with-2-symbols since it was brought to my attention that the question would be better suited to ...
1
vote
1answer
47 views

How to prove $L \notin \texttt{DSPACE}(f)$

I want to prove that a language $L$ is not in $\texttt{DSPACE}(f(n))$, the class of languages that a deterministic Turing machine can decide with fixed tape length of $f(n)$ (wiki). That is, I want to ...
1
vote
0answers
14 views

How to adapt proof of the ND time hierarchy theorem for alternate definition of NDTM?

For reference, the version of the nondeterministic time hierarchy theorem in question is this one: The relevant portion of the proof in question (also from Arora-Barak) is here: Arora-Barak define a ...
1
vote
0answers
16 views

What's the difference between Acfg and ALLcfg

In computational theory, and talking about CFGs, Turing Machines, and so forth I haven't a satisfactory explanation or definition for what ATM means versus ALLTM or the same or similar uses with ...
1
vote
0answers
26 views

Theory for programs that are “embedded” in other programs?

We can make the following distinctions: (I will use the term "program" and "machine" as synonyms). A (baseline) machine. This can be formalized by a Turing machine. It receives an input, and computes ...
1
vote
1answer
72 views

How to prove that {<M1, M2> : M1 and M2 are two DFAs and L(M1) $\neq$ L(M2)} is in NL?

My idea is to find a turing machine which recognizes this language in $\log N$ space, could anyone give me some clue on how to find such turing machine?