# Questions tagged [turing-machines]

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

197 questions
Filter by
Sorted by
Tagged with
39 views

### Detailed proof for multitape turing machines

I am aware of the fact that for every Multitape Turing Machine there exists a Single tape Turing Machine that accepts the same language. However, the proof of this fact is a high level proof in most ...
732 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 ...
100 views

### Functional abbreviation for Inst expression in Turing's 1936 paper

In Turing's 1936 paper "On Computable Numbers", For a Turing Machine $M$, $Inst(q_i S_j S_k L q_l )$ means that if $M$ scans symbol $S_j$ under $m-configuration$ $q_i$, then the symbol ...
290 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" ...
182 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 ...
143 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 ...
119 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 ...
110 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 ...
53 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 '...
36 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?
146 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 ...
121 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 ...
224 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 ...
60 views

169 views

### Evidence integer multiplication is in linear time?

After millenia of quest we have identified two $n$ bit integers can be multiplied in $O(n\log n)$ time. Please refer details in https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-...
3k views

### Did Alan Turing's student Robin Gandy assert that Charles Babbage had no notion of a universal computing machine?

Robin Gandy was a student of Alan Turing. Gandy did an analysis of Babbage's Analytical Engine (see 'Gandy - The Confluence of Ideas in 1936' quoted in 'Herken, Rolf - The Universal Turing Machine—...
283 views

### Does Depth-First-Search admit a quasilinear time algorithm in mutitape Turing Machine model?

Depth-First-Search (DFS) has a quasilinear (i.e.,$\widetilde{O}(m+n)$) time algorithm in random access model (RAM). I am curious about whether DFS still admits a $\widetilde{O}(m+n)$ time algorithm in ...
54 views

### Asymptotic time required to simulate a Turing machine M for k steps

Problem: Given an encoding of a Turing machine M and a natural number k as input, find the output of M (given a blank tape) after k steps. Wikipedia's page on EXPTIME-complete says it takes O(k) time ...
252 views

### Uniform mortality problem for Turing Machines

Consider the following generalisation of the mortality problem for Turing Machines. Given a Turing Machine $M$. Is there a bound $k_M$ such that starting from any configuration $c$ machine $M$ ...
284 views

### Turing Machines as Coalgebras

I'm looking to write a survey on the method of representing the dynamics of state-based computation within the framework of coalgebras. So far I've managed to find papers on coalgebra representations ...
152 views

### Why does the Placid Platypus function grow faster than any computable function?

I came across the Placid Platypus function $PP(n)$ today, defined as the minimal number of states needed for a turing machine that prints a string of $n$ ones and halts. This function is claimed to (...
170 views

304 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-...
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 ...