Skip to main content

Questions tagged [turing-machines]

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
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 ...
Nehul Jain's user avatar
0 votes
0 answers
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 ...
Minseo Kim's user avatar
0 votes
0 answers
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 ...
mousetail's user avatar
  • 166
5 votes
1 answer
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 ...
Wei-Cheng Liu's user avatar
3 votes
1 answer
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 ...
Jo Bain's user avatar
  • 31
0 votes
0 answers
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 ...
Muhammad Ikhwan Perwira's user avatar
1 vote
1 answer
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 ...
Muhammad Ikhwan Perwira's user avatar
1 vote
1 answer
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 (...
Mirmir12's user avatar
0 votes
0 answers
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. ...
user1701057's user avatar
0 votes
1 answer
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 ...
matt_rule's user avatar
  • 111
1 vote
2 answers
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 ...
Simon Walker's user avatar
2 votes
1 answer
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 ...
Dudi Frid's user avatar
  • 231
0 votes
0 answers
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.,...
study.isLove's user avatar
1 vote
2 answers
45 views

Rice theorem - $EQ_{TM}$

Could use some help understanding if Riceโ€™s theorem applies to the following language: $๐ฟ = \{\langle ๐‘€\rangle \lvert M \text{ ๐‘–๐‘  ๐‘Ž ๐‘‡๐‘€ ๐‘Ž๐‘›๐‘‘ } ๐ฟ(๐‘€) \subseteq ๐ธ๐‘„_{TM} \}$ (where $EQ_{TM} =\{...
user169627's user avatar
2 votes
0 answers
25 views

Relative running times of equivalent Turing machines with arbitrary and binary alphabets

The book "Computational Complexity: A modern approach" by Sanjeev Arora and Boaz Barak contains the following claim: Claim 1.5 For every $f : \{0, 1\}^โˆ— \to \{0, 1\}$ and time-constructible ...
Gaurav Chandan's user avatar
0 votes
1 answer
63 views

Why get this P=NP? What I am doing wrong?

As we know, all NP problems are decidable because there is a NTM that can solve them in polynomial time. To my knowledge, any NTM is equivalent to a DTM. Thus, if NP problems can be decided by a NTM e....
Ali.A's user avatar
  • 11
1 vote
1 answer
61 views

Why does ISA includes instruction for logical operation?

I'm a junior student in Electronic Engineering. Recently, I learned about Gรถdel's incompleteness theorem. One of the concepts related to this theorem is Gรถdel numbering, which shows that every logical ...
MS Keane's user avatar
0 votes
1 answer
129 views

Analog computers more powerful than turing machines?

Ignoring quantum mechanics for a moment, is it true that analog computers are more powerful than turing machines? for example an analog computer can add two irrational numbers together, but a turing ...
JobHunter69's user avatar
1 vote
1 answer
40 views

What is the difference between $ L_e$ and $E_{TM} $?

What is the difference between $L_e = \{ \langle M \rangle | L(M) = \emptyset \}$ and $E_{TM} = \{ \langle M \rangle | \text{M is a turing machine and L(M)} = \emptyset \}$? $L_e$ is not RE and $E_{...
Cesare's user avatar
  • 11
3 votes
1 answer
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โˆช๐ฟ...
IVRODB's user avatar
  • 31
1 vote
1 answer
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$. ...
Dan D-man's user avatar
  • 534
-1 votes
1 answer
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?
josh hackentoff's user avatar
0 votes
0 answers
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 ...
Benicio Agüero's user avatar
1 vote
1 answer
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 ...
Air Homely's user avatar
0 votes
1 answer
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 ...
KylerAce's user avatar
2 votes
1 answer
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 ...
lonewolfx86's user avatar
0 votes
1 answer
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 ...
hitchens's user avatar
9 votes
14 answers
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 ...
JobHunter69's user avatar
1 vote
1 answer
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 ...
2080's user avatar
  • 191
0 votes
1 answer
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 ...
2080's user avatar
  • 191
2 votes
0 answers
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.
Clément Dato's user avatar
3 votes
0 answers
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 ...
2080's user avatar
  • 191
0 votes
0 answers
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 ...
Meatabix's user avatar
0 votes
1 answer
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 ...
Nerincet Vonwthaud's user avatar
0 votes
0 answers
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-...
Jane's user avatar
  • 1
0 votes
0 answers
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 ...
task manager's user avatar
2 votes
1 answer
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 ...
PranksterSabeleye's user avatar
2 votes
0 answers
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 ...
2080's user avatar
  • 191
0 votes
1 answer
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 ...
Max0815's user avatar
  • 103
0 votes
1 answer
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 ...
Mark's user avatar
  • 1
3 votes
1 answer
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 ...
Joe's user avatar
  • 133
1 vote
0 answers
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, ...
confusedcius's user avatar
2 votes
1 answer
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 ...
PranksterSabeleye's user avatar
2 votes
1 answer
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 ...
Lex's user avatar
  • 21
2 votes
1 answer
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 ...
Zee's user avatar
  • 243
0 votes
3 answers
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 ...
Luke Hutchison's user avatar
0 votes
5 answers
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 ...
Wisdom Iwueze's user avatar
2 votes
2 answers
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 ...
Muhammad Zulqarnain Malik's user avatar
4 votes
1 answer
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 ...
math boy's user avatar
  • 359
0 votes
0 answers
55 views

The formal proof that one Turing Machine computes one specific function

I have asked one similar question QA_1 "The formal proof that one Turing Machine recognizes one specific language" and the answer fills the part "It does not generate any string that is ...
An5Drama's user avatar
  • 203

1
2 3 4 5
โ€ฆ
52