This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.

learn more… | top users | synonyms

1
vote
2answers
35 views

Is there a way to prove that a Turing machine computes the function we designed it to?

Say we design a simple Turing machine that adds two numbers together. Is there any way to formally prove that the machine actually computes the function we 'know' it does? Is there a general method ...
2
votes
1answer
12 views

Savitch theorem and its assumption

famous Savitch theorem states: For any function $f\in\Omega(\log(n)), \text{NSPACE}(f(n)) \subseteq > \text{DSPACE}((f(n))^2).$ Why we need an assumption that $f\in\Omega(\log(n))$? Thank ...
1
vote
1answer
21 views

Turing recognizable - $B = \{a^n b^n c^n \}$

Question: My answer is no, because it loops forever. But I am a bit unsure if this is the right answer.
0
votes
0answers
25 views

all recursive functions are turing computable

I'm studying with the book computability and logic(boolos). In chapter 5, the theorem is proved, indirectly, by showing that (recursive => abacus) & (abacus=> turing). But I want to prove ...
2
votes
0answers
36 views

How are weakly universal Turing machines actually defined?

For what I know, the definition of a universal Turing machine is something along the lines of the following (of course, details might vary from source to source): A Turing machine $M$ is called ...
0
votes
0answers
28 views

Designing a Turing machine for Binary Division

I'm trying to design a TM to binary divide 2 numbers. The best approach I've found is the method: division as repeated subtraction, but I don't know if there's a fastest way or an easier way. ...
1
vote
1answer
91 views

A function given a string ( a program) accepts it if the next program which halts does so in an odd number of steps… is it turing computable

A function which given a string returns 1 if the next program halts with an odd number of steps and 0 otherwise. Is this function computable f(s)=1 if w halts in odd number of steps where w>s and ...
0
votes
2answers
62 views

Is this integral less than infinity?

Assume the following integral: $$ \int\limits_{-\infty}^{\infty}\frac{f\left(x\right)} {BB\left(\lceil abs\left(x\right)\rceil\right)}\mathrm{d}x $$ Where $f\left(x\right)$ is any computable ...
4
votes
1answer
38 views

Doubt about neural networks that allegedly compute beyond the Turing limit

The question is about a new result by Cabessa & Siegelmann. http://binds.cs.umass.edu/papers/2014_cabessa.pdf : "In this context, we show that the so-called plastic recurrent neural networks ...
0
votes
0answers
20 views

How to compute the solution for this linearized diffusion-reaction system (separation of variables)?

Let $\Omega=(0,a), a>0$ and functions $u(x,t), v(x,t)\in\mathbb{R}$. Consider the diffusion-reaction system $$ \partial_tu=\Delta u+\gamma f(u,v)\text{ for }x\in\Omega,t>0\\\partial_t v=d\Delta ...
2
votes
3answers
67 views

Turing Machine divisibility by 6 [closed]

I need to design a TM to check if a binary number can be dividied by 6. I don't know how to design it. Thanks
3
votes
2answers
40 views

Have anyone ever thought of continuous analog Turing machine?

Have anyone ever thought of continuous analog Turing machine? The machine adopts continuous (from R) the input data from the tape, It moves to a different state depending on the value on the tape. On ...
2
votes
1answer
47 views

Understanding Turing Machines: Recognizable and Decidable langauges

I've searched tons of resources and while conceptually I understand the turing machine itself and what it does- I'm a bit stuck on Turing Recognizable and Turing Decidable languages and I'm not sure ...
2
votes
1answer
66 views

There are more languages than programs?

I am reviewing some Turing machine material...and I come across this the set of all programs are countable (convert them into binary string, each of which represent an integer) whereas the set of ...
1
vote
1answer
21 views

Deciding set of all Turing machine codes of TMs accepting languages of cardinality $\leq 10$.

Problem: I need to show that the following language is decidable and if not, if $S$ or $\overline{S}$ is partialy decidable language. $S=\{w_e\;|\;|L(M_e)|\leq 10\}$ That is set of all Turing ...
1
vote
2answers
32 views

Unprovable behavior of a turing machine

The wikipedia-article for the P-NP problem [1] says there are three possible answers to the P-NP-problem: $P=NP$ $P\neq NP$ $P=NP$ is independent of ZFC The third possible solution seems to be ...
0
votes
2answers
25 views

Do there exist infinite sets of non-halting programs such that every program in the set computes every other program in the set?

Do there exist infinite sets of non-halting programs such that every program in the set computes every other program in the set, and only programs in that set? I know there exist programs which ...
0
votes
1answer
48 views

How to prove whether a language is decidable and/or semi-decidable (or neither) using reduction?

I think I understand the basics of reduction, however I'm far from confident with using the techniques. I have a couple of examples that I'm struggling with: L1 = {< M > | M accepts an infinite ...
1
vote
2answers
68 views

Must an algorithm terminate?

I am confused. Sometimes i read about terminating and not terminating algorithms. I almost always read these things in the context of turing machines. This means to me: There are algorithms which ...
0
votes
1answer
22 views

How could I design a turing machine that prints all natural numbers on its tape in order?

How one could implement a turing machine that prints all natural numbers of its tape in order. Two consecutive numbers are separated on the tape with the symbol #. The tape should look like this: ...
0
votes
0answers
35 views

How could I modify a Turing machine that attempts to move the head past the leftmost square(crash) on some inputs so that it doesn't crash at all?

Suppose that M is a TM that crashes on some inputs. How would I modify M so that the new machine accepts the same language but does not crash on any input ?
-1
votes
1answer
61 views

Show that every finite subset of $\{0,1\}^*$ is recursive [closed]

How can I show that every finite subset of $\{0,1\}^*$ is recursive ?
0
votes
1answer
57 views

Read-only Turing machine recognizes only regular languages?

Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages. According to wiki : A read-only Turing machine or ...
0
votes
0answers
25 views

Does 3-SAT reduce to 3-CNF-SAT?

I know that SAT goes to 3-SAT and SAT is reducible to CNF-SAT and CNF-SAT is reducible to 3-CNF-SAT but is 3-SAT reducible to 3-CNF-SAT? They are not the same thing though right because cnf makes it ...
0
votes
0answers
19 views

Design a Turing Machine to compute the function

I'm tasked with designing a Turing Machine able to run in this Turing machine simulator With the function: f(x) = { x : x < 3 x + 3 : x ≥ 3 Where input: ...
1
vote
1answer
47 views

Is a Turing machine on an arbitrary (finite) alphabet equivalent to one on {0, 1}?

Brief context: I'm trying to understand why a Universal Turing Machine exists, on a tape with alphabet $\{0, 1\}$. I think I can see that a $3$-tape Turing machine can represent a Universal Turing ...
0
votes
1answer
18 views

State Change in a Turing Machine(Computer of Integer Function)

Im trying to learn how TM can be used as a computer of integer functions. I have this problem The text books gives the construction as follows I understand that intially the R/W head will be ...
0
votes
1answer
7 views

Moves in a Turing Machine

In a Turing Machine i understand that δ(q,x) is a transition function that results in a Change in ID. What does δ(q, Xj) =(P, y, L) mean.I understand that L stands for move left.Is P the new state ...
0
votes
1answer
12 views

Intersection of Turing Machines Languages

Given a Turing Machine A and a Turing Machine B, how can I know if the intersection of the Languages of both Turing Machines is non empty? L(A) $\cap$ L(B) $\neq$ 0
0
votes
1answer
39 views

Proof that a certain language is Turing Decidable

$$L_1 = \{\langle R,S \rangle \mid \text{$R$ and $S$ are regular expressions and }L(R) \subseteq L(S)\}$$ $$L_2 = \{\langle M\rangle\mid \text{$M$ is a DFA that accepts $w^r$ whenever it accepts $w$} ...
2
votes
1answer
180 views

Construct a deterministic Turing machine that decides the language $L=\{w\in\{a, b\}\mid w\text{ contains an occurrence of }ab\}$

So we are asked to construct a deterministic Turing machine. I have constructed a Turing machine, but I'm not sure if it's correct. Here is my Turing machine: For the question above, I'm just ...
0
votes
2answers
27 views

difference between A* and 2^A*

let A be any input alphabet then what is the difference between A* (kleen closure of A) and 2^A* ?
0
votes
1answer
34 views

Prove that the class of Turing Decidable Languages is strictly larger than class of Context Free Languages

Prove that the class of Turing decidable languages is strictly larger than the class of context free languages. (Give a language that is Turing decidable, but which violates the pumping lemma for ...
-1
votes
1answer
52 views

Draw a Turing machine that recognizes $\{w \in\{0,1\}^*\,|\,w\text{ contains even number of 1's}\}$

Draw a Turing machine that recognizes the language $\{w \in \{0,1\}^*|w \text{ contains even number of 1's}\}$ This is where I am at:
3
votes
1answer
40 views

Abstract machines that compute primitive recursive functions

What it the simplest (least powerful) abstract machine that can compute primitive recursive sets, i.e. sets whose characteristic or indicator function is primitive recursive? ...
0
votes
1answer
65 views

Language decidability and Post's theorem

I have the following exercise on decidability: Show that the language $L$ is decidable if and only if there exist decidable languages $A$ and $B$ such that $L=\{x\;|\;(\exists y)[\langle x, ...
1
vote
1answer
35 views

How is $ BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $

I'm not able to understand how $BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $ Can any body explain this to me in simple terms. Any help on this is highly appreciated.
0
votes
0answers
31 views

Design Turing Machine

Design a single-tape Turing machine with input alphabet {0, 1} to decide the language $$\{ x\in\{0,1\}^* \mid \#(0,x)=2\cdot\#(1,x)\}.$$ Could someone give me clarification on how to approach and ...
0
votes
1answer
17 views

Need help in understanding proof “approach” and meaning for “1st order Theory of dense linear orders w/o endpoints is PSPACE complete”

So in my class we are giving a proof for 1st order Theory of dense linear orders w/o endpoints is PSPACE complete. The proof that it is in PSPACE is basically to reduce TQBF. Let $\phi = \exists ...
1
vote
0answers
24 views

Are languages that contain the empty string Turing-Decidable?

Given a language that is Turing-Decidable, if you add the empty string to the language then is the new language Turing-Decidable? I am very confused at this problem because from my understanding the ...
0
votes
0answers
15 views

Is a Turing Machine which must check every single possible string ever a decider?

When classifying a language, I've constructed a Turing Machine to recognize it. However, to do so the machine must check every single possible input string from an alphabet. Since this is an infinite ...
0
votes
0answers
26 views

What class of probability distributions do probabilistic turing machines induce?

What class of probability distributions is induced by the class of probabilistic turing machines? Is there a precise characterization?
0
votes
0answers
16 views

Turing machine that accept L = {ww} in linearithmic time

I was wondering if there is a way to design a deterministic turing machine that accept the language L = {ww} with a time complexity of O(n log(n))
0
votes
0answers
18 views

Ph has log complete set

how can I show that PH has a ≤log m -complete set if and only if it collapses I am CS major and I do not have much Idea on how to do mathematical proofs
0
votes
1answer
23 views

Why is there, for every language L in NP, a Turing machine with polynomial memory that also accepts L?

So my question is the title, but I also have a question about something else. If you have a problem, how can you determine the reason that it is in NP. So for example: given a directed graph with $N$ ...
1
vote
0answers
29 views

Reducability and decidability language

i am new to this course called Theory of Computation. And my teacher asked to solve this ... i dont know how to do it... please help Consider the langauge L_inf : A turing machine M belongs to L_inf ...
0
votes
0answers
40 views

What is the maximum amount of steps a Turing machine needs to take before you know it won't accept the input?

So for example, we take a Turing machine $M$ with alphabet $\{0,1\}$ and 10 states, where $q_0$ is the initial state and $q_F$ is the accepting state. For a certain algorithm or calculation $M$ is ...
1
vote
0answers
109 views

Turing machine ( exponentiation )

How do I design Turing machine for exponential function $a^x$? I found this explanation http://philpapers.org/archive/LEMATM , but its too complicated. Could someone tell me please, is there another ...
0
votes
0answers
44 views

Are elimination of lambda and closure expressions always possible?

As proofed the lambda calculus, which uses higher-order functions (passing functions as arguments), is turing complete. This makes me wonder if one of the following statements is true: Are ...
-1
votes
1answer
19 views

If Language $L_1$ is accepted by a Pushdown Automata and Language$ L_2$ by a Turing Machine, Is $L_1 \cup L_2$ accepted by a Pushdown Automata?

Let $L_1$ be a language recognized by a Pushdown automaton and let $L_2$ be another language recognized by a Turing machine. Is $L_1 \cup L_2$ recognized by a Pushdown automaton? Prove your answer.