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

learn more… | top users | synonyms

-2
votes
0answers
23 views

If a language is NP-complete and its complement is NP, is the complement NP-complete?

If i know that for some language $L$ that is is NP-complete and its complement $\overline{L}$ is in NP, what can be said about NP-completeness of $\overline{L}$?
0
votes
0answers
30 views

Is $f$ which returns the $n$-th word in $\overline{H_{TM,\epsilon}}$ computable?

The question itself: Let $f:\mathbb{N}\to\Sigma^\star$ be such that $f(n)$ returns the $n$-th word in $\overline{H_{TM,\epsilon}}$ (which is the complement of the language of TMs which accept ...
0
votes
0answers
40 views

Is ATM with decidable TM also undecidable? [on hold]

Is ATM with decidable TM also undecidable ? We can tell the UTM to go to reject state if it sees a reject state from TM so it can be decidable. $$ATM = \{\langle M, w \rangle \mid \text{\(M\) is a ...
-4
votes
1answer
64 views

Order classic notions of computability by power

I need some help with a question. I'm currently studying for an exam and I could therefore use some help with this following question: Order the following formalisms (but one) according to their ...
2
votes
1answer
68 views

Turing Machine with additional finite memory of size $n$

The question itself: Let us define a generalization of Turing Machines to include a finite memory of >size $n$. We denote such a Turing Machine formally as: $M_{mem} = (Q, Σ, γ, ...
3
votes
1answer
55 views

Undecidability of REGULAR_TM (Detail within Proof)

I'm reading through Sipser's Intro to the Theory of Computation for a class, and I'm having trouble understanding one of the examples in the book. The example shows how $REGULAR_{TM}$, defined as the ...
3
votes
2answers
55 views

Given a r.e. (recursively enumerable) language, L, how many Turing machines semi-decide L?

$L\subseteq \{0,1\}^*$ Since the language is r.e. there is definitely at least one Turing Machine that semi-decides the language. I'm thinking that if you have one Turing Machine that semi-decides ...
1
vote
1answer
51 views

Pseudocode algorithm to check encoding of Turing machine

My question goes like this: Write an algorithm (in pseudocode) that on input $w$, checks that $w$ encodes a valid Turing machine $\langle M\rangle$. e.g, you need to validate that the structure is ...
5
votes
1answer
3k views

Are all languages in P?

Are all languages in $\mathbf{P}$? Note: The definitions of all the symbols and functions here follow the document [1]. The following is my attempt to answer the question. Assume that we design a ...
0
votes
1answer
11 views

Transition and configuration of Turing machine

In my lecture I have examples about 0 -> R (which means if it's 0, move Right) or 0 -> x, R (replace 0 with x and move Right) but I don't quite understand about the 0, 0 -> R expression. What is the ...
0
votes
2answers
31 views

Proof for TM accepting any PDA-language

How do you suggest I go about proving this: Give a short, basic outline of a proof that Turing machines can accept all languages accepted by PDAs. You are allowed to use a non-standard Turing ...
-3
votes
0answers
20 views

Create Turing Machine using transition table

So we started learning about Turing Machines and I do not quite fully understand it. My teacher wants us to create a Turing Machine by writing out the whole transition table, that counts in binary. We ...
-4
votes
0answers
26 views

Is it possible to draw a turing machine decider state diagram from a given language

Lets say I have a language X where it has the alphabet 0 and 1. and the number of 0s must be twice the number of 1s is it possible to draw a turing decider state diagram for this language and if ...
0
votes
2answers
47 views

What happens after the accept state if there are still letters in the string in a Turing machine?

Lets say there is a turing machine $M$ where \begin{align*} M &= (Q, \Sigma, \Gamma, \delta, q_1, q_{accept}, q_{reject}) \\ Q &= \{q_1, q_2, q_3, q_{accept}, q_{reject} \} \\ Σ &= \{0, ...
2
votes
2answers
61 views

Language of TMs such that one state is visited most often

To be safe, let me start this question by giving the definition of a TM I will be using: A TM is some $M = (Q, \Sigma, \Gamma, q_0, \delta, q_F)$, where $Q$ is the finite state set, $\Sigma \subset ...
0
votes
0answers
43 views

Calculating Big-O

I was asked to find the O-complexity of the algorithm accepting the language {0^(2^k) | k>=0} meaning the length of a string in the language will be of a power of two. (using a turing machine) $ The ...
1
vote
0answers
43 views

Language of Turing machines that never visit some given state

Can someone help me to determine and prove if the following language is decidable or not? I tried to think on some reductions but I can't figure it out... $$A=\{\langle M\rangle|\text{$M$ is $TM$ ...
1
vote
1answer
46 views

Understanding Levin's Universal Search

I am having troubles understanding Levin's universal search method. In Scholarpedia, http://www.scholarpedia.org/article/Universal_search, it is claimed that “If there exists a program $p$, of length ...
3
votes
1answer
100 views

What is the fastest addition algorithm on a turing machine?

What's the asymptotic running time of the fastest algorithm for adding two $n$-digit decimal numbers on a Turing machine? To specify, the input is of the form $a_1+a_2$ where $a_1$ and $a_2$ are ...
0
votes
0answers
19 views

On Karp reduction

Assume a complete problem for a class $\mathcal C$ is in $P/poly$ and at each $n$ assume that the advice string is $s_n$ of length $n^c$ for a fixed $c>0$. Assume that $SAT$ of $n$ length input ...
0
votes
0answers
46 views

Why is $coNP\subseteq NP/O(1)$ and $coNP\subseteq NP/O(\log n)$ not same as $coNP=NP$?

If $NP\subseteq P/log\implies P=NP$ why does $coNP\subseteq NP/O(1)$ or $coNP\subseteq NP/O(\log n)$ not implies $coNP=NP$?
3
votes
1answer
20 views

How to identify strongly confluent cellular automatas?

Lets represent a class of cellular automata as a finite, unidimensional bit array state : [Bit], plus a rewrite rule ...
0
votes
1answer
54 views

Implications of Halting Problem being unsolvable?

I came across a confusing situation when reducing the Halting Problem (HP) to the Blank Tape Accepting Problem (BP). We know that since HP can be reduced to BP, BP is decidable $\implies$ HP is ...
1
vote
1answer
33 views

Prove Undecidability Without Using Rice's Theorem

Show that checking if a TM accepts some input string of length greater than some constant $k$ is undecidable. Here the constant $k$ is publicly known. I tried solving this problem by trying to reduce ...
-1
votes
1answer
53 views

Building an undecidable T-Grammar

I am asked, "Show that these T-Grammars constitute a set of languages that are undecidable. Do this by building a T-Grammar for a Turing machine description. For a starting point you might think about ...
1
vote
1answer
27 views

Turing Machine that always returns a blank tape

Is it possible to construct a Turing Machine such that given any finite input on a tape $s$, it clears the tape in a finite amount of time? I have used such a TM as an intermediate step to show a ...
0
votes
1answer
27 views

Is function application actually a memory manipulation algorithm?

I thought about how in lambda calculus (and many implementations of functional programming languages) function (lambda) application and lambda itself, as a construct, are "primitive things", usually ...
3
votes
1answer
31 views

Is there an example of a recursive language which is not context sensitive?

I have been looking for a prototypical language for recursive languages (decidible) which is no context sensitive without success. For instance $a^*$ is prototypical of regular languages, $a^nb^n$ for ...
-1
votes
1answer
64 views

How can a Turing machine accept infinite number of inputs? [closed]

How it is possible for a turing machine to process an infinitely long input ?
-1
votes
1answer
51 views

Turing tests and humans

How are the questions framed in Turing tests? I mean what factors would one consider before framing questionnaire for the Turing Test.How the questions should be framed to make the test unbiased for a ...
3
votes
1answer
102 views

Whatever that can be done using algorithm can be done using Turing machine

In 1937 how was Alan Turing so sure that all that can be done using algorithms can be implemented using a Turing machine? Since that period many new algorithms were implemented. What was his ...
0
votes
1answer
97 views

Prove whether this problem is decidable or undecidable [duplicate]

So I am reviewing my notes for this problem, and I cant seem to understand how this problem works. Say we have M, and M accepts an input that makes it visit every non-halting state. I convinced ...
0
votes
0answers
42 views

Does Turing Completeness imply the existence of a Universal Program?

Please correct me if at any time my definitions are wrong. Suppose we have a programming language $L$ over some set $D$ with semantic (partial) n-ary functions $\varphi^n:D \to (D^n \to D)$. Assume $L ...
0
votes
0answers
38 views

How do I show that M1, M2 are two Turing machines such that L(M1) ⊆ L(M2)?

I am currently studying for a midterm tomorrow and my professor gave us links to backtests online. This is problem #3 in the following back quiz: ...
-3
votes
1answer
50 views

Prove that TM does not decide this language

So my problem is how can I show that this TM does not decides this language. $$L = \{a^nb^nc^n\ |\ n \geq 0\} $$ It might be a basic problem and seem silly to you but still I do not know how to ...
1
vote
2answers
53 views

Turing machine states, lost in the jungle

There is a lengthy discussion going on at the English Language & Usage StackExchange site suggesting various synonyms for dead code, and it got me wondering about an angle that wasn't covered -- ...
1
vote
1answer
43 views

A question about halt (or stop) of Turing machine

I try to understand something: At Turing machine we have two stats: $q_{accept}$ and $q_{reject}$. Now, if machine $M$ runs on word $w$ (I hope I write it right...) and the final configuration is: ...
0
votes
1answer
35 views

Turing Machines: decidability and bounds checking

I am wanting to show that it is decidable that a Turing machine M, on input w, ever attempts to move its head past the right end of the input string w. I'm assuming I construct a TM which shifts the ...
0
votes
0answers
40 views

Is there a name for a useful Turing-like machine that is more powerful (meaning accepts more languages) than a Turing machine?

Disclaimer: I'm a software engineer with only an undergrad education and have never published or anything so please forgive any minor notation or jargon blunders - but of course feel free to point ...
1
vote
0answers
25 views

Decidability Proof of $A_{Cfg}$

I am a beginner to complexity theory and I came up with the following proof of decidability of $A_{Cfg}$ = {$<G,w>|G$ is a context free grammar that generates string $w$} The Turing machine ...
1
vote
0answers
32 views

Busy beaver construction system [closed]

I want to construct a busy beaver TM which has the alphabet $\Sigma = \{1,2, X\}$ and $X$ is the blank symbol. I want to do this using 3, 4 and 5 states (means one just for halting, so 3 states = 2 ...
6
votes
1answer
147 views

Prove n! is fully time constructible

We just finished our "Time constructability" lesson in class last week, and we, for example's sake, showed that $n^k, 2^n$ are fully time constructible, i.e. there exists a (multi-tape deterministic) ...
4
votes
0answers
30 views

Why does using an encoding trick like Gödel numbers make a register machine universal?

Here the author describes the Random Access Stored Program machine and the problem of indirect addressing. The author states: But this does not solve the problem (unless one resorts to Gödel ...
0
votes
1answer
52 views

A recursive language minus a recursively enumerable language results in a recursive language?

I know that a recursively enumerable language minus a recursive language results in a recursively enumerable language, but I'm confused with the above question. Aren't all recursive languages also ...
26
votes
4answers
5k views

Theoretical machines which are more powerful than Turing machines

Are there any theoretical machines which exceed Turing machines capability in at least some areas?
2
votes
1answer
95 views

How to find left-hand side of tape on a Turing Machine?

I am pretty new to Turing Machines and am trying to figure something out. So let's say I have a tape with input 0 0 1 0 0 1 The language is twice as many 0's ...
2
votes
1answer
47 views

How to write the turing machine processing operations?

I have this Turing machine example given in my book: For the language $0^n1^n$. I understand how it works because it's very similar to a Finite State Machine. But what I want to know is the ...
1
vote
1answer
43 views

Implementation-level description of a Turing Machine

I am new to Turing Machines! I need to work on an implementation-level description of a Turing machine that decides the language L = an where n is a Fibonacci number. I know Fibonacci numbers ...
0
votes
0answers
146 views

Trying to show if two languages are recognizable or not

I have two languages that I am trying to prove are recognizable or not: Let L1 = {<\M, w> : M is a Turing machine that accepts string w and does not accept string ε}. Is L1 recognizable? Prove ...
3
votes
1answer
40 views

Unary notation representation in Turing Machine

What can be a good convention to represent positive and negative integers in unary notation on a Turing machine? I want to design a Turing machine which acts as a subtractor.So should I partition the ...