Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
2,565
questions
1
vote
2
answers
62
views
Why can one define a Turing Machine by its "description"?
I read Sipser's "Introduction to the Theory of Computation" a while ago. I am confused that in the book it is stated that a Turing machine can be defined by its "description" such ...
- 113
2
votes
1
answer
53
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 ...
- 21
0
votes
0
answers
19
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 ...
0
votes
0
answers
54
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
5
votes
1
answer
162
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 ...
- 237
3
votes
1
answer
46
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
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 ...
1
vote
1
answer
30
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
1
answer
42
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
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. ...
- 31
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 ...
- 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 ...
- 33
2
votes
1
answer
112
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
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.,...
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} =\{...
- 73