# Questions tagged [turing-machines]

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

1,568 questions
Filter by
Sorted by
Tagged with
1answer
46 views

### How strong is an oracle that avoid don't-halt

Consider such an oracle: Given a turing machine, return the halting state it falls on, or arbitary result(but don't stuck in) if the TM doesn't halt. How strong is a TM with the oracle? Can the ...
0answers
20 views

### How to measure the length of the program on Turing Machine?

In Kolmogorov complexity, there is a notion: length of the shortest program that describes the data. I can use Lempel-Ziv compression to estimate this value. What if I want to estimate this value by ...
0answers
28 views

### A condition for $\emptyset \neq S\subset RE$ under which $L_S \notin RE$

I read some computation theory lecture notes and after citing and proving the proposition: $\emptyset \in S \Rightarrow L_S = \{\langle M \rangle : L(M)\in S\} \notin RE$ it says that $\emptyset\in S$ ...
0answers
23 views

### Which of the following languages a decidable? [on hold]

I have a question about the decidability of the following languages: 1. L = { | ab ∈ L(M) and M accept only w with |w| >= 10} 2. L = { | M only accept a finite number of words} 3. L = { | L(M) = ∅ ∨...
1answer
57 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 ...
3answers
428 views

1answer
16 views

### What is the difference between a collection of Turing Machines and a family of Circuits?

Given a Collection of Turing Machines $T_1, T_2, T_3,...T_n$ where $T_1$ denotes that the Turing machine can only take in an input of size 1. Is there any difference in computational power to a family ...
1answer
19 views

### Simulating multi-tape turing machines by single-tape TM

In "Computational Complexity: A modern approach", Arora and Barak proof the following Claim: Define a single-tape Turing machine to be a TM that has only one read-write tape, that is used a input, ...
1answer
138 views

### Can an alphabet for a Turing machine contain subsets of other alphabets?

For example; Is {0,1,{a,b,c},d,e} a valid alphabet to form a language over and is it usable in any context?
1answer
84 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 ...
2answers
145 views

### The Halting problem proof is wrong?

First, let's see the pseudocode proof of halting problem: P(x) = run H(x, x) if H(x, x) answers "yes" loop forever else halt Then we have a ...
1answer
104 views

### Is the infinite program Turing-recognizable/decidable?

Imagine we have a program which does an infinite loop: while(true){loop} We run the program on a linux machine(assume the compilation is ok), then this linux ...
1answer
72 views

### Which languages, decided by a turing machine are decidable?

How do I decide if a language is decidable and/or semi-decidable? I have theses languages: a) { < M > | L(M) ⊆ 0*} b) { < M > | L(M) contains at least one word of even length} c) {...
1answer
41 views

### How can the VC-dimension of Turing machine be finite?

The VC-dimension of a hypothesis class $\mathcal{H}$ is defined to be the size of the maximal set $C$ such that $\mathcal{H}$ cannot shutter. This paper shows that the VC-dimension of the set of all ...
1answer
195 views

### Prove that it is undecidable whether a given LBA accepts a regular set

I know for an LBA the emptiness problem is undecidable. However I am not clear on how to reduce the halting problem of Turing machines to this as LBAs are strictly computationally less powerful than ...
0answers
33 views

1answer
38 views

### If the human brain is a Turing machine then how is it able to ascertain that certain problems are undecidable? [closed]

I recently read about the idea that the human brain might be a Turing machine (or Turing complete). If that is true then how is the brain able to reason that a certain problem is undecidable for e.g. ...
3answers
144 views

### Can undecidability theorems be detected by a machine? [closed]

this question was originally written in mathoverflow, but a comment recommended me to rewrite it as a CS question. This is not a mathematically formalized question. I'm sorry for that but think it's ...
0answers
59 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 ...
1answer
42 views

2answers
2k views

### Turing Machines: What is the difference between recognizing, deciding, total, accepting, rejecting?

I have seen a remark saying "we usually say that a turing machine accepts/rejects a string, while it decides a language" Is this correct? As I have also seen places where we mention a Turing machine "...
1answer
13 views

### Turing Machines: What is the difference between the language realised by a problem and the language for which the TM accepts on?

A decision problem A corresponds to the language L1 if L1 contains all of the solutions to A. A language L2 is defined as the set of all inputs to which a TM halts and accepts. What is the link ...
1answer
17 views

### What is the link between the language defined by the Turing Machine and the algorithm that the Turing machine implements?

What is the link between the language defined by the Turing Machine and the algorithm that the Turing machine implements? I.e. What is the link between the language and the algorithm