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
-4 votes
0 answers
48 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?
JobHunter69's user avatar
-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 = ...
Nicolò Bonacorsi's user avatar
3 votes
1 answer
569 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
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, ...
confusedcius's user avatar
2 votes
1 answer
99 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 ...
PranksterSabeleye's user avatar
2 votes
1 answer
23 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
52 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
-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 ...
maya cohen's user avatar
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 ...
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
1 vote
2 answers
73 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
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 ...
math boy's user avatar
  • 353
0 votes
0 answers
52 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
  • 193
0 votes
1 answer
61 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 ...
An5Drama's user avatar
  • 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 ...
Javier's user avatar
  • 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 ...
maya cohen's user avatar
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. ...
wytubev's user avatar
  • 13
0 votes
1 answer
76 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 ...
Diode's user avatar
  • 1
0 votes
3 answers
75 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!
mikealexx's user avatar
1 vote
0 answers
25 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 ...
cartman's user avatar
  • 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 ...
Slim Shady's user avatar
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 (...
rus9384's user avatar
  • 1,632
2 votes
1 answer
68 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 ...
ErroR's user avatar
  • 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 ...
rus9384's user avatar
  • 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 ...
zokina's user avatar
  • 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 ...
sadcat_1's user avatar
  • 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 ...
David's user avatar
  • 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$, ...
maya cohen's user avatar
1 vote
1 answer
52 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 $ ...
maya cohen's user avatar
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 $...
NiStack's user avatar
  • 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)$? ...
ampersander's user avatar
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 ...
NiStack's user avatar
  • 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 ...
maya cohen's user avatar
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 ...
Dilara's user avatar
  • 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 ...
maya cohen's user avatar
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 ...
maya cohen's user avatar
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 ...
Just Curious's user avatar
2 votes
1 answer
78 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 ...
Luca Sambuca's user avatar
-2 votes
1 answer
65 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 ...
Just Curious's user avatar
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 ...
Jean Abou Samra's user avatar
2 votes
2 answers
347 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 ...
Robert Wegner's user avatar
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 ...
Yarin's user avatar
  • 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 ...
Aditya 's user avatar
  • 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 ...
Trev's user avatar
  • 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 ...
Theorynoob's user avatar
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 ...
Ma Joad's user avatar
  • 119
4 votes
1 answer
167 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 ...
Emolga's user avatar
  • 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 ...
Aditya 's user avatar
  • 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 ...
Nabisa's user avatar
  • 1
-3 votes
1 answer
85 views

is this a contradiction? "stating there are an infinite number of programs but that a program cannot be infinitely long is a contradiction"

i saw this comment here : David Deutsch says "number of atoms in universe is finite", but then says "number of programs of all finite lengths is infinite". Contradiction? "&...
robotrage's user avatar
  • 101

1
2 3 4 5
51