Questions tagged [turing-machines]
Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.
2,537
questions
0
votes
1
answer
31
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
-4
votes
0
answers
52
views
Proof that strong AI exists?
If turing machines are capable of simulating physics, then they should be able to simulate a human brain. Isn't that enough to prove the existence of strong AI?
- 153
-2
votes
0
answers
23
views
How can i describe this Turing Machine?
We assume that the tape of the Turing machine is infinite on both sides. Initially, the tape head is positioned on any cell, and each cell of the tape contains a blank symbol. The set of states is Q = ...
3
votes
1
answer
588
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
0
answers
39
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
2
votes
1
answer
102
views
Is matching pairs sufficient?
This is a snapshot from Dexter C. Kozen - Automata and Computability, Lecture-35, Undecidable problems about CFLs. My question here is that, why should we check triples (3-element substrings)? Why not ...
2
votes
1
answer
25
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
2
votes
1
answer
53
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
-1
votes
0
answers
8
views
How to Prove or Disprove Language Acceptance with Limited Error by a Non-Deterministic Turing Machine?
Let M be a non-deterministic Turing machine (NDTM) that accepts a language L if and only if:
for each $ x\in L $ M doesn't accept x for at most m branch(path) calculations.
for each $ x\notin L $ M ...
- 201
0
votes
3
answers
69
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 ...
- 111
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 ...
1
vote
2
answers
74
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 ...
4
votes
1
answer
120
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 ...
- 353
0
votes
0
answers
53
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 ...
- 193
0
votes
1
answer
62
views
The formal proof that one Turing Machine recognizes one specific language
When given one grammar, we can formally prove that it can recognize one language using QA_1
Since Kleene's Theorem gives the equivalence between the regular grammar and the NFA, we can also use QA_1 ...
- 193
0
votes
0
answers
43
views
Multitape Turing Machine to accept power of 2 length 0's string?
I have been trying to find a multitape Turing Machine in order to accept a input string which consists on 0's and whose length is a power of 2:
However, Im getting troubble finding it, because I dont ...
- 1
1
vote
1
answer
37
views
Is $L = \{ \langle G,k\rangle \mid G $ has a simple cycle at length $k \}$ in P or in NP
$ L = \{ <G,k> |\ G \ has \ a \ simple \ cycle
\ at \ length \ k \} $
I think this language is in NP but my friend thinks this language is in P.
NP proof:
if a graph has a simple cycle of a ...
- 201
1
vote
1
answer
51
views
Proof that nondeterministic TM runs in exponential time
Consider a nondeterministic TM $M$ that takes as input another TM $M'$, a string $x$ and integer $k$. $M$ decides if there exists a string y s.t. $|y| \leq |x|^2$ and $M'(x, y)$ accepts in $k$ steps. ...
- 13
0
votes
1
answer
81
views
Mapping Reduction from HALT?
I've been given a task to determine whether L={〈M〉|M is a TM that loops on the input c (a constant)} is decidable. I can prove co-L is recognizable so I figured a reduction from HALT to co-L would ...
- 1
0
votes
3
answers
76
views
Is $\{\langle \langle M\rangle, q\rangle\mid M(\varepsilon)$ enters state $q$ infinite times$\}$ not in RE?
I'm trying to use reduction $\overline{HP} \leq L$, but I just can't think of a way to do so.
Any help would be appreciated!
1
vote
0
answers
26
views
Hardwiring advice (bit string) into Turing machine
In paper, page 5, 1st paragraph, it is stated that:
Notice that an n-state Busy Beaver, if we had it, would serve as an O(n log n)-bit advice string, “unlocking” the answers to the halting problem ...
- 11
0
votes
0
answers
42
views
How do people working on the Busy Beaver function keep track of all the turing machines?
I'm a CS undergrad so forgive me if this question isn't formulated well. I got curious about the Busy Beaver function recently, and it got me wondering how all the n-state Turing machines are kept ...
- 101
0
votes
0
answers
25
views
Effectively universal Turing machines and Turing-completeness?
An effectively universal Turing machine $T$ is a Turing machine for which there exists a recursive reduction $f$ such that $\forall A:U(A)=T(f(A))$, where $A, f(A)$ are finite sequences of symbols (...
- 1,632
2
votes
1
answer
69
views
Time complexity of specific variant of Turing Machine
Assume a variant of a one-tape deterministic Turing Machine that reads and writes on the portion of the tape that the input $w$ appears (like linear bounded automata).
My question is, how we could ...
- 1,910
0
votes
1
answer
36
views
Undecidability of the exactly-1-in-k halting problem
The problem:
Given $k>1$ Turing machines decide if for every possible input exactly one of them halts.
Is this variant of halting problem undecidable?
Intuitively, it seems that it must be not ...
- 1,632
0
votes
1
answer
53
views
Are there some additions that a Turing machine cannot perform
The total number of Turing machines is the cardinality of the set of natural numbers. Now consider the following functions
f1(x) = x + 1
f2(x) = x + 2
f3(x) = x + 3
and so on
Since the total number ...
- 1
4
votes
1
answer
296
views
Is the language L = {<M> | There exists an M' that stops on the same input words, but L(M) ≠ L(M')} in RE or R?
Is the language $$L = \{M | \exists M' \text{ that stops on the same input words but L(M)} \neq L(M')\}$$ in RE or R?
I suspect that it's not in RE, since you'd have to first know for M all the inputs ...
- 219
-1
votes
1
answer
57
views
Turing Machine language, Undecidable, reductions
I have exam next week about automata theory, languages and computation. I struggle with reductions (Undecidability). For example for this two problems, and need to check first if the language is ...
- 11
1
vote
0
answers
68
views
Do there exist infinitely many languages that are RE-complete?
I would like to prove or disporove: there exists infinitely many languagess that are RE-Complete.
Here is my attempt of the proof.
Let $L$ be any RE-complete language. Define a padded version of $L$, ...
- 201
1
vote
1
answer
53
views
Proof or disproof Fin = Fin-Complete $ Fin = \{ L \in \Sigma^* : |L| $ is finite and greater than 0 $ \} $
$ Fin = \{ L \in \Sigma^* : |L| $ is finite and greater than 0 $ \} $
Proof or disproof Fin = Fin-Complete
Where Fin-Complete means that for every $ L_1,L_2 \in Fin $ there exist a valid reduction $ ...
- 201
2
votes
2
answers
146
views
Prove that there aren't any complete languages
Prove that there isn't a complete language over a given alphabet $\Sigma$. That is, there is no $C \subseteq \Sigma^*$ such that every $L \subseteq \Sigma^*$ is Turing-reducible to $C$.
Attempt: Let $...
- 47
3
votes
1
answer
82
views
Is there a language $L$ such that $L \in DSPACE(1) \setminus DTIME(1)$?
It is a very straightforward question.
I know that the following holds, and I know why it holds:
$DTIME(f(n)) \subset DSPACE(f(n))$
However, is there a language $L \in DSPACE(1) \setminus DTIME(1)$? ...
- 133
0
votes
2
answers
61
views
Prove the existence of a language L over the alphabet Σ = {1} such that L ∌ RE and L ∌ CoRE
I attempted to create a language $L_1$ = {$<M>| L(M) = 1^*$} and prove using a reduction that $L_1$ ∌ RE and $L_1$ ∌ CoRE by showing that $HP ≤ L_1$ and $\overline{HP}$ $≤ L_1$.
But my ...
- 47
1
vote
1
answer
88
views
Proof or Disproof if $ L $ is a Regular language then it has to be that $ L\leq HP $
Proof or Disproof
if $ L $ is a Regular language then it has to be that $ L\leq HP $
$ HP=\{<M,x> | M \ halts \ on \ x \} $
Regular language is a language that can be expressed with a regular ...
- 201
0
votes
2
answers
97
views
$L =$ { $\langle M \rangle$ | $M$ moves left on at least one input }
Is $L =$ { $\langle M \rangle$ | $M$ moves left on at least one input } decidable? What would the proof look like?
Intuitively, I would say it's undecidable: We cannot predict if a given TM ever ...
- 11
0
votes
1
answer
37
views
proof or disproof if $ L_1 \subseteq L_2 $ then $ L_1 \leq L_2 $
proof or disproof
if $ L_1 \subseteq L_2 $ then $ L_1 \leq L_2 $
I tried to think with HP and the empty language because HP is in RE and the empty language is in R but how do I prove this does not ...
- 201
0
votes
1
answer
95
views
Proof or disproove $L_1 , L_2 \in RE \setminus R $ such that $ L_1 \cup L_2 \in R $ and $ L_1 \cap L_2 \in R $
Proove or Disproove
$ \exists L_1 , L_2 \in RE \setminus R $
such that $ L_1 \cup L_2 \in R $ and $ L_1 \cap L_2 \in R $
I tried to use the languages
the union is $ \sigma^* $ and the ...
- 201
1
vote
1
answer
36
views
Decidability terms clarification
I just need some clarification regarding the different terms we use in theoretical computer science, especially regarding decidability.
Decidable:
A language $L$ (a set of strings) is decidable if ...
- 11
2
votes
1
answer
80
views
How to write down a program of a Turing Machine with just two states that, when given the empty tape as inputs, halts after 6 steps
I’m definitely not a computer science expert, but I find this topic extremely interesting - due to this interest, I’ve recently enrolled in a class about Turing Machine.
The lecturer assigned to us an ...
- 21
-2
votes
1
answer
67
views
Is the "intersection" of the special Halting Problem with a language always undecidable?
I'm exploring the decidability characteristics of a particular language formed by the intersection of two languages, specifically in the context of the Halting Problem. The languages are defined as ...
- 11
3
votes
1
answer
355
views
Turing degree of some functions related to Rice's theorem
Rice's theorem asserts that as soon as $f$ is non-trivial (i.e., non-constant), and extensional (i.e., $f(M) = f(M')$ as soon as $M$ and $M'$ are codes of Turing machines with the same behavior, in ...
- 427
2
votes
2
answers
348
views
Algorithm that generates verification program from solution program of NP problem
I don't know complexity class theory well so I might make some categorical errors, but I will try to ask this question anyways.
Suppose you have written a function in some programming language which ...
- 121
0
votes
1
answer
61
views
Is the function $f: \mathbb{N} \rightarrow \mathbb{N}$ where $f(n) = 2^n$ computable in polynomial time using TM?
Assuming that the input $n$ is given as a decimal number.
I was asked to prove whether the function $f: \mathbb{N} \rightarrow \mathbb{N}$ where $f(n) = 2^n$ is computable in polynomial time using TM ...
- 275
2
votes
1
answer
54
views
Is explicitly explaining the case where the Turing Machine loops forever essential to proving reducibility?
I am asking this in the context of the following question:
Let N be a non-deterministic Turing Machine. We say that N faces a dilemma if at some point in its working, it encounters a situation where ...
- 123
1
vote
1
answer
61
views
How far out can one determine a program is halting?
Suppose we have a finite set of programs, say, something like every Turing machine with 2 states and 7 symbols. After running all of them for a very long time, we've narrowed it down to a small subset ...
- 296
0
votes
1
answer
13
views
Transform OTM for Problem π to DTM ∈ DSPACE(n)
Given an Oracle Turing machine ($OTM$) that solves Problem π in max. 2n space, so $O(n)$ space and $O(n^2)$ time.
Is there a DTM that can solve $π$ in $O(n)$ space if time doesn't matter? (The length ...
- 11
1
vote
1
answer
169
views
Is the problem of "finding the output given the algorithm halts" not computable?
For simplicity, let's assume all Turing machines print 0 or 1 on the tape. Consider an algorithm $A$, which, given any Turing machine $T$ as the input, outputs $x\in \{0,1\}$, satisfying the condition ...
- 119
4
votes
1
answer
169
views
Deciding whether a Turing machine decides a language $L$ in at most $n^2$ steps
Let $L$ be a language for which there exists some turing machine deciding it in at most $n^2$ steps.
Is it decidable whether a given turing machine $M$ decides $L$ and runs in at most $n^2$ steps?
I ...
- 223
0
votes
1
answer
33
views
How to check whether a given language is decidable when the definition contains some predetermined machine
Let $L = \{\langle M, W \rangle \mid M $ is a Turing machine, w is a string and some Turing Machine $M_1$ exists such that w does not belong to $L(M) \cap L(M_1)\}$
I am unsure of how to deal with ...
- 123
0
votes
0
answers
35
views
Build a Turing machine that will count the units written in a row (without omissions)
Build a Turing machine that will count the units written in a row (without omissions) (their number does not exceed n) and write their number in the number system with the base n +1, here n=3+[N](mod ...
- 1