# Questions tagged [turing-machines]

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

2,564 questions
Filter by
Sorted by
Tagged with
51 views

### How to prove a problem is EXP hard

Summary of the problem: Given an alternating time turing machine ($M$), a polynomial $p(.)$ and a string ($w$), is it EXPhard to find if $M$ accepts $w$ using not more than $p(|M|+|w|)$ space? My ...
17 views

### Acceptance of n length word that is accepted by Turing Machine in m steps

let x a word with length of n an it is accepted by Turing machine in m steps. I think that if m<=n, there would be infinite number of words (all the words that starts with x) that are accepted by ...
52 views

### How many states does a 2-symbol turing machine need on average to compute a N bit number?

The busy beaver problem asks what is the largest number computable by a 2-symbol N-state Turing machine, however, most numbers however are not re-presentable by a smaller program. For a sufficiently ...
• 166
133 views
+50

### Prove that $n$ is a time-constructible function

I am reading Arora and Barak's book: "Computational Complexity: A Modern Approach". On page 16, the authors wrote: A function $T: \mathbb{N} \rightarrow \mathbb{N}$ is time constructible if ...
44 views

### Naming Turing machines paired with input

Is there an established name for pairs $(\langle M \rangle, w)$ of a Turing machine $M$ (or description thereof) together with an input word $w$? Such pairs often arise as elements of sets for ...
• 31
13 views

### How simple addition operation performed with just one instruction by BitBitJump?

According this: https://en.m.wikipedia.org/wiki/One-instruction_set_computer Its instruction has 3 operands, the meaning is: copy the bit addressed by a to the bit addressed by b and jump to the ...
1 vote
29 views

### What are the most minimalistic assembly's mnemonics to make complete turing machine?

Disclaimer: I'm a computer engineering student, not a computer science. Pardon me for mistakenly using computer science terms. I want to design computer architecture with the most minimalist design as ...
1 vote
33 views

### Turing Machine that deletes a word after accepting it?

I want to make a TM $\text{TM}_{\text{Erase}}$ that given another TM $M$ and a word $w$, will accept iff $M$ accepts it and deletes $w$ from the input line. My solution was using two symbols (...
• 11
21 views

### L in NP and L is coNP-hard=>NP = coNP

How can I prove this: given this 2 sentences 1 <=> 2: There exists a language L ∈ NP that is coNP-hard. NP=coNP. the direction from 2 to 1 I can prove using the concept of NP-cpmplete and etc. ...
28 views

### Is it possible to use a non-Turing-complete language to describe the steps to build a Turing Machine?

First of all, it is impossible to use a Turing-incomplete language to simulate a Turing-complete one (see link) However, is it possible to use a Turing-incomplete language to describe the steps to ...
• 111
1 vote
32 views

### Does modifying input space change space complexity?

The auxiliary space analysis that involves modifying the input array can lead to "unfair" situations. Examples: Consider that an algorithm that uses O(N) memory and does not need to ...
110 views

### Deducing upper bound for Boolean Circuit size from well-known algorithms

Given an algorithm A for computing binary function $f$. Assuming that A runs in time $t(n)$, what could we say about the size of the minimal Boolean circuit C that calculates f? I think that it ...
• 231
34 views

### Given a TM $M$ Denote $L(M), L_{rej}(M), L_{non-halt} (M)$, Is $L(M)\in R$ implies $L_{rej}(M)\in R$?

Question: Given the following definitions for a Turing machine $M$: $$L_{rej}(M) = \{w \in \Sigma^* : q_0w \vdash_M^* uq_{rej}v\}$$ Basically, represents the language of words that $M$ rejects (i.e.,...
1 vote
45 views

• 11
48 views

### Computability- relationship between R, coRE and RE

I am trying to think of a question that discusses the relationship between RE, coRE and R. Namely- is it true that for all For every language 𝐿1∉ RE there exists a language 𝐿2∉ coRE such that 𝐿1∪𝐿...
• 31
1 vote
101 views

### Polynomial solutions, one less

Let $L$ be a language in the class $FP$ of all polynomial-time solvable problems. The class $FP$ is defined by having a TM $M$ s.t. for any $x$ it computes in polynomial time a $y$ s.t. $(x,y)\in L$. ...
• 534
29 views

### Acceptance of Turing Machines is NP-Hard?

I had a question in my exam 'Show that the acceptance of turing machines is NP-Hard'. How do I go about this question?
37 views

### Equivalent definition of a PTNDTM?

$NP$ is the class of problems with a polynomial time non-deterministic turing machine which can determine whether an input is in a certain language or not. It can be seen as polynomial time ...
1 vote
40 views

### Why we can reduce $A_{TM}$ to $ALL_{CFG}$, but we can not reduce $A_{TM}$ to $E_{CFG}$

If a $PDA$ can be constructed to check whether a string is not a computation history for a Turing Machine. Like in the proof of $ALL_{CFG}$ is not decidable. Then we can construct a $PDA$ that accepts ...
51 views

### Why Does Computable Analysis Use Type 2 Turing Machines Over Type 1 TM's?

I've been researching formal models for computing with real numbers and came across the field of computable analysis built on top of specifically the type 2 Turing machine, which allows for ...
710 views

### Definition feels contradictory (Computational Complexity Theory)

I studied a definition for time complexity: Let $M$ be a deterministic Turing Machine. The running time of $M$ is said to be: for a function $t: \mathbb{N} \to \mathbb{N}$ ($\mathbb{N}$ is natural ...
40 views

### Using reducibility to prove a language that accepts $\lambda$ and either loops or accepts other strings is undecidable

I am new to the reduction style of proof so I am hoping to get some help on this problem. Let $L=\{〈M〉:M$ accepts the empty string and does not reject any string$\}$. Prove $L$ is undecidable. My ...
8k views

### Why is the Turing machine considered effective computation if it's not realizable due to the Bekenstein bound?

According to the Bekenstein bound, Turing machines are not realizable in real life. So why are they accepted as the standard for effective computation? You may as well consider more powerful machines ...
• 324
1 vote
65 views

### Constraints on the order of program semantics given by an enumeration of turing-complete system programs

There are Turing-complete systems like Jot where every natural number represents a valid program. This results in a Gödel numbering. Now, if the semantics of the programs were, say ...
• 191
25 views

### Generating all unique (tape content, head position) possibilities for a Turing Machine

Assuming a single tape (which extends infinitely in both directions) Turing Machine, If its head and tape contents start at position $0$ and the tape contents are only extended to the right, then it ...
• 191
20 views

### Is it decidable whether a Turing machine is universal? [duplicate]

I imagine the answer was negative, but I cannot find a proof of it.
• 131
26 views

### Fastest possible (direct?) simulation of one tape turing machines by a small one tape Universal Turing Machine

The paper The complexity of small universal Turing machines: a survey (.pdf) includes the following chart of the then (2011) smallest known Universal Turing Machines. The ones marked as rectangles ...
• 191
169 views

### Turing Machine transition table for checking a palindrome

Using a Turing machine. If the input tape of the machine consisted of a string of 0's and 1's, how would you approach the problem given that the output of the machine should be 1 or 0 respectively ...
22 views

### Are there any example of practical application of counter machines?

I am currently working on a presentation over how counter machines are as effective as Turing machines. During my research, I found out that random access machines are an improved version of counter ...
22 views

### Prove that the complement of the language L = { <T> : T is a Turing machine that runs in polynomial time } is not turing recognizable

To show that L is not Turing-recognizable, we can use a reduction from the complement of the ATM problem (ATM'). However, I'm not sure about how we would prove that the complement of L is not Turing-...
• 1
9 views

### Does a Language Accepted by a Non-deterministic Turing Machine with Zero Errors Necessarily Belong to Class R

It is said that a non-deterministic Turing machine M accepts a language L with m errors if and only if: For every x in language L, M does not accept x in at most m calculation routes. for every x ...
33 views

### Decidability of whether for a given $G$, $L(G)=\Sigma^+$? (or $L(G)=L$ where $L$ is fixed beforehand

If $G$ is a CFG, is it decidable whether $L(G)=\Sigma^+=\Sigma^*\setminus\{\epsilon\}$? I have no idea which in direction to go. I feel like it is undecidable, but can't seem to find any proof. I ...
65 views

### Compiler that compiles to a Universal Turing Machine (UTM) tape program?

With Universal Turing Machines I mean the Turing Machines with fixed transition functions, proven by Yurii Rogozhin in his paper "Small universal Turing machines" to be capable of universal ...
• 191
28 views

### Is this formulation for a turing machine proper?

Say I define a turing machine with the following states $$Q \in \{q_0, q_1, \dots, q_n, q_{\text{halt}}\}$$ Here, $n$ is guaranteed to be finite. Then, also have a set of rules where I do something ...
• 103
60 views

### If a language L over a finite alphabet A has both a subset and superset that are Turing-recognizable, does this make L Turing-Recognizable too?

"Let A be a finite alphabet, and let L1 and L2 be two Turing-recognisable languages over A such that L1 is a proper subset of L2, i.e. L1 ⊂ L2 but L1 ≠ L2. Let a language L over the alphabet A ...
• 1
608 views

### Can the minimisation operation be seen from a programming language perspective?

If $f$ is a total function $\mathbb N^k\to\mathbb N$, and $g$ is a total function $\mathbb N^{k+2}\to\mathbb N$, then we say that $h:\mathbb N^{k+1}\to\mathbb N$ is definable by primitive recursion ...
• 133
1 vote
41 views

### Alphabet of Turing Machines and Diagonalization

When we are using a diagonalization argument, does it matter what the alphabet of the Turing machine we are using to do the diagonalization is? I think it does but I'm not 100% sure. For example, ...
• 246
114 views

### Is matching pairs sufficient?

Book PDF: https://vishub.org/officedocs/13770.pdf Pg 253 of book This is a snapshot from Dexter C. Kozen - Automata and Computability, Lecture-35, Undecidable problems about CFLs. My question here is ...
33 views

### I am struggling to define the space complexity of a turing machine

I have a problem where I have a class A which is made up of problems which is solveable with a TM with space complexity O(logn). I now need to prove that the problem, where an input string of length n ...
• 21
56 views

### How to interpret Universal Quantifier in Alternating Turing Machines?

I am trying to read about Alternating Turing Machines (ATM) that have both existential and universal quantifiers for all their internal states. Given that these models are conceptual, I tend to ...
• 243
71 views

### What is the name of the theory that says that Turing equivalence is universal, and Turing machines are maximally computationally powerful?

In the Chomsky hierarchy, level 0 grammars include all languages that can be recognized by a Turing machine. There is no level -1 (which would represent the class of languages that cannot be ...
2k views

### If the set of Turing machines is countably infinite, how can a Turing machine always have a finite set of states?

I have only begun studying this subject and have only completed the first few chapters of the Elements of the Theory of Computation. I have seen the answers (on this site and elsewhere) saying that ...
124 views

### How to write a turing machine program for any given problem?

I'm learning about Turing machine program,i want to know how we write a Turing machine program about any given problem, like a string is accepted by Turing machine, program (for a Single Tape Turing ...
127 views

### Is the Turing machine the only framework to analyse limits of computation?

In Theory of Computation lessons, the limits of computation are usually analyzed within the framework of Turing machines, so if something isn't solvable with Turing Machine, then we consider this ...
• 359