Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
2,224
questions
-1
votes
0answers
5 views
Compare powers of PDM and FSM with Turing machine
Compare powers of PDM and FSM
with Turing machine.
5
votes
0answers
62 views
A Turing machine with each cell accessed at most $10$ times has an equivalent NFA
I am confused by the following claim:
Let $T$ be a (decider, single-tape) Turing machine with the property that for every input, every cell on its tape is accessed at most $10$ times. Then there is a ...
0
votes
1answer
35 views
Are turing machines & equivalents with infinite sized random programs still turing machines?
Are turing machines with an infinite program tape that is completely random, or another example is a Game of Life simulation on an infinite randomly initialized grid, still turing machines, so to ...
0
votes
1answer
12 views
How to simulate an NTM using a DTM?
I've seen questions about how an NTM could simulate a DTM and this seems pretty straightforward to me. However, my text book says you can also simulate an NTM using a DTM.
How would this work? I'm ...
0
votes
0answers
14 views
Turing machine with polynomial complexity on Jflap
I would like to ask a question: I have this very simple Turing machine. Simply by subtracting the numbers A and B, given the input M (A, B, C, D) =.
Using the Step function on Jflap, complete the ...
1
vote
0answers
18 views
How can a non-deterministic Turing Machine be converted to a deterministic TM with a witness-input?
This 2014 paper by Barak and Goldreich defines the notion of a universal set $S_{\mathcal{U}}$ as the set of all tuples $(M,x,t)$ such that the non-deterministic machine $M$ accepts the input $x$ in $...
-1
votes
0answers
16 views
Describe how to build a non-deterministic Turing machine that accepts the set of all element prefixes of $L$, i.e, $PREFIX(L)$
Describe how to build a non-deterministic Turing machine that accepts the set of all element prefixes of $L$, i.e, $PREFIX(L)$.
Hello, I have been trying to solve this problem, my intuition tells that ...
-2
votes
0answers
28 views
Prove by reduction that the language $L^♦ = \{N | N \text{ is a } TM \text{ and } L(N) \text{ is a recursive language}\}$ is not recursive
Prove by reduction that the language $L^♦ = \{N | N \text{ is a } TM \text{ and } L(N) \text{ is a recursive language}\}$ is not recursive.
Hi, I've been strugling with this problem since yesterday, ...
0
votes
1answer
35 views
How Universal Turing Machines can do something if a machine doesn't accept?
In our Computability & Complexity course, we wanted to show that $ALL_{TM}\notin RE$. To do that, we have seen the following claim (I'm summarizing it):
Denote the languages:
$ALL_{TM}=\{(M)|L(M)=\...
0
votes
0answers
7 views
In the Recursion Theorem, does obtaining a description of SELF increase the length of the program?
In the following video, he mentions that x <- <SELF> (x obtaining a description of itself) is a "legal" operation for a Turing Machine to make. https://youtu.be/5yO_l2w0wIA?t=93
My ...
0
votes
0answers
15 views
Is a computational model that can instantly access any storage address and can access any arbitrary number of them at once more powerful then a TM?
This would be a computational model that would have unbounded space. But with a jump command that can access and do operations on any finite number of cells at once. Actual calculations would take ...
-1
votes
1answer
33 views
Turing machine to find maximum of an infinite set
Given a set that is infinite but still countable, does a TM exist that goes over every element in the set and finds the maximum?
Is this a computable function?
1
vote
1answer
30 views
Is the following function computable? is it total?
I have the following function:
$f : N \to N $ and $f(n)= \max_{i \leq w(n)} g_{i}(n)$
with $g_1, g_2,...g_{w(n)}$ being an enumeration of all computable functions $g_i$, and $w : N \to N$ being any ...
0
votes
0answers
21 views
How to show that the set of all turing machines that halt on a blank tape form a recursively enumerable set
I learned in my class that set of all Turing machines that halt on a blank tape form a recursively enumerable set. I was told that you can prove it using an argument similar to the diagonalization ...
0
votes
0answers
12 views
Simple examples of Recursive Enumerable Functions
My understanding of Recursively Enumerable Functions is that they're recursive functions, but for some values of the arguments you put into the function they will stop and give an answer, and for ...
1
vote
0answers
25 views
Graph based on strings of turing machine
For a $\Sigma$ with characters $0,1,$#$,\sigma_1,...,\sigma_m$. I have any $M$ that is a deterministic turing machine. Fix a $n$ (natural). i look at the following graph constructed from the turing ...
0
votes
2answers
95 views
How do I find out what SPACE a language has?
I want to know how I can calculate/find out which SPACE a language has, because I don't get it. I have this definition
Definition: Fix a function $f: \mathbb N → \mathbb N$. We say that a language $A$...
2
votes
3answers
88 views
Proving that a class equals NP ∩ coNP
We say that a non-deterministic Turing machine is nice if for every input x the following holds:
• Every computation path returns either ’accept’, ’reject’ or ’quit’.
• There is at least one non-quit ...
0
votes
1answer
189 views
Turing machine with infinite tape alphabet
Given is the modified definition of a TM where everything is equal except for one change: $\Gamma=\Sigma\cup \mathbb{N}\cup\{\square\}$
How do I prove that there is a TM $M$ for any language $L\...
1
vote
2answers
59 views
Is it accurate to contrast a Turing machine with finite automata by claiming the former is stateful and the latter is pure?
Recently, I was having a debate with a friend about what it would mean to create a machine that ZKSnarks (proves) itself. I tossed the word pure machine out there while describing what I hypothesized ...
1
vote
1answer
26 views
Can distirbuted processing, OS processes or even threads be used to simulate a non deterministic turing machine adequately on small datasets?
For example for the traveling salesman problem which is a proven NP-Complete problem, if we spawn a thread at each node in the graph such that each of those threads will, in turn, spawn as many ...
1
vote
2answers
35 views
We cannot recognize a set of languages as the language themselves
"We cannot recognize a set of languages as the language themselves"
What is the meaning of the line and why we cannot do it and how is the encoding of TM is helping in that?
1
vote
1answer
36 views
Is Self-Modifying Turing Machine equivalent to NTM or TM?
Let SMTM be Turing Machine, but the commands recorded in which can change to others in some random way (for example, choose with a 50/50 probability the command to move to the right or move to the ...
0
votes
1answer
37 views
Small Turing machine accepting single complicated input?
This imprecise question is about a simple example for the following problem.
I would like a Turing machine with few states that accepts only inputs which look complicated to the naked eye.
Of course ...
0
votes
0answers
21 views
Designing a Turing machine which recognises that doubles the input string and concatenates the invert of the input
I have to design a Turing machine which takes a input string $a^{*}$.
$a^{*} = \left \{0,1 \right \}^{+}$
Following this pattern where S is the input string:
$$
S_{n} = \left \{0, n=0 \right \} \\ \\...
0
votes
1answer
43 views
In a rigorous mathematical sense, what is the significance of Turing-completeness?
I know that Turing-completeness is the ability to simulate a Turing machine, and from what I've read, the reason why we should care about Turing-completeness is that it demonstrates that a machine can ...
2
votes
2answers
66 views
Why is a Language L(M) {has at least 10 strings} turing recognizable and L(N) {has at most 10 strings} is not?
Why is a Language L(M) {has at least 10 strings} recognizable and L(N) {has at most 10 strings} is not?
...
0
votes
1answer
34 views
kolmogorov complexity for finite Language?
In lectures my professor proved that there is no Turing machine that for every x it calculates k(x).
On the other hand, I saw a claim online that for finite language L there is a Turing machine that ...
0
votes
0answers
39 views
Finite Number of Turing Machines that stop after k steps?
For this question suppose Alphabet for input is {0,1}.
Given:
L={<M> | M stops on every input after maximum 1000 steps}
My professor claimed that there is a ...
2
votes
1answer
40 views
Is the language of PSPACE Turing Machines decidable?
Let
$$L_{\text{PSPACE}}=\{\langle M\rangle : M \text{ is a TM using a polyspace amount of memory}\}$$
Is $L_{\text{PSPACE}}$ decidable?
I don't think we can use Rice's Theorem because this doesn't ...
1
vote
1answer
21 views
Definition a Turing machine (which may or may not halt) as a function... notation?
I would like to define a Turing machine as follows.
Let Z be an alphabet, and let L be the set of all sentences of this alphabet. For instance, Z={0,1}, then L is the set of all binary sentences.
A ...
0
votes
0answers
24 views
Is the set of all halting programs for all universal Turing machines recursively enumerable?
I understand that one can use dovetailing to recursively enumerate the domain of a UTM.
However, I am trying to recursively enumerate the domain of all possible UTM.
My starting point was to use a ...
5
votes
3answers
3k views
How Turing Machine Can Never Stop?
My professor discussed the following Turing machine M' on input (,x):
Generate number n
Run M on X, for n steps
If M stops, accept
I don't understand No.3
If we are running M on input X for final ...
0
votes
0answers
50 views
Are all Turing machines Turing complete?
I have recently been reading up on TOC, and had this thought, which does not seem to be answered explicitly anywhere.
They way I have understood it, a system is Turing complete if it can simulate any ...
1
vote
2answers
51 views
Confused about Turing Recognizability
If Turing Recognizability means a T.M. will either halt on input w if w is in the language, or run forever if w is not in the language.
How can we know the language is Turing Recognizable if we run ...
0
votes
0answers
24 views
Undecidability of a set of Turing Machines
Considering the following set, I have to say if it is undecidable, decidable or semidecidable:
$$S_1 = \{y | \forall n \text{ the Turing Machine } M_y \text{ does not accept any string of length } n\}$...
1
vote
0answers
14 views
Design a two-tape deterministic Turing machine M that recognizes the language L3= {x#(0^k) #y : x, y ∈ {0, 1}* , x = y ∧ |x| = k}
I'm having a hard time trying to write a two tape Turing machine
I wanted to first think Oh all I'd have to do is scan from left-to-right till I find the strings that matches the accepted strings) ...
3
votes
1answer
85 views
How is the time complexity of a non-deterministic Turing machine defined?
I read different things online about this:
In Sipser, p. 283. The time-complexity of a NTM is defined as the maximum number of steps it uses on any branch on any input of length n.
So this is only ...
0
votes
1answer
24 views
What does c represent in Sipser's explanation of the modified post correspondence problem Introduction to the Theory of Computation book?
I'm supposed to perform actions corresponding to the different steps in Sipser's explanation of the Modified Post Correspondence Problem, but I'm not sure I understand the third step.
The part I'm ...
1
vote
1answer
34 views
Showing Turing machines are more computationally powerful than Finite State Machines
I've been pondering on whether Finite State Machines, particularly Mealy machines, can describe any computable function as Turing machines do. However "Mealy-computability" does not seem to ...
0
votes
0answers
24 views
Turing Machine that accepts L(M1) = {x^n y^2n z^n | n ∈ N}
I'm trying to design a Turing machine that accepts all strings in the language $$\{x^{n}y^{2n}z^{n}|\ n\in N\}$$ but I'm having trouble getting it to accepts when n> 1, for some reason it rejects ...
1
vote
0answers
15 views
Proving set of register machines that halt before k steps for some input is non-recursive
Given an enumeration of register machines $R_n$ that take a single natural number as input, and a constant $k$, the function $f$ is defined as:
$$
f(n) = \begin{cases} 1 & \exists m \text{ such ...
0
votes
3answers
238 views
How it's possible decide CNF by having a turing machine that decide SAT?
Suppose we have a Turing machine $M$ as black box that decide $SAT$ problem. Now suppse we have a $CNF$ formula $\phi$ with $n$ variables. How it possible checking satisfiblity of $\phi$ and then ...
0
votes
0answers
19 views
Is there any problems with equating Turing Machines with Algorithms and Language with Problems?
In a lot of the online explanation of complexity theory, the author proposes the following.
"The definition associated with complexity theory (e.g., definition of
NP) is phrased in terms of ...
0
votes
1answer
43 views
Turing machine accepting square
I'm trying to figure out following assignment and I could use your help, because I'm stuck.
Task:
Construct a Turing machine accepting words in format $1^k$, where $k=n^2$, $n$ being an integer. ...
1
vote
1answer
50 views
Is the language containing Turing machine $(M_1, M_2)$ such that $L(M_1) \cup L(M_2) = \Sigma^*$ decidable?
We are given two Turing machines $M_1$ and $M_2$ and we wish to decide whether the union of the language $L(M_1)$ accepted by $M_1$ with the language $L(M_2)$ accepted by $M_2$ coincides with $\Sigma^...
-2
votes
3answers
105 views
What is the point of encoding universal turing machines?
I am unable to understand why do we need to encode turing machine at all? I heard that we are trying to build a programmeable turing machine but can't relate how encoding it will make this ...
1
vote
1answer
32 views
A turing machine L takes a machine <M> which has to halt at for least n Inputs
I've been wondering about this problem for a while:
Say we have L = { <M>, n | M has to halt for at least n Inputs}
and multitapes are simulating various inputs bla bla
How do I count how many ...
-2
votes
1answer
77 views
Halting problem is undecidable proof-:
Confused with this proof. I will point my confusions here.
what is R(M)? They say it is representation of turing machine but what is it exactly? Is it tuples of turing machine? How do we decide w is ...
0
votes
0answers
20 views
A query regarding equivalence of Parallel vs. Serial cells Turning Machine
Given: A Turing machine (set of programs) that behaves as follows:
It has some fixed number of states $(S)$ and binary alphabet $(0/1)$.
For some constants $k, p, (k<N, p< N)$:
Its read/write ...
