Questions tagged [turing-machines]

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

2,223 questions
Filter by
Sorted by
Tagged with
47 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 ...
34 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 ...
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 ...
13 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 ...
18 views

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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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$...
87 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 ...
189 views

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) ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
42 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. ...