Questions tagged [turing-machines]

A Turing machine is an idealized model of computation consisting of a finite-state control, an infinite tape holding information, and a read head positioned somewhere over the tape. Turing machines are used in computability theory to reason about the limits of computation, to provide a formal definition for an algorithm, and to provide formal models for nondeterminism.

Filter by
Sorted by
Tagged with
0 votes
0 answers
28 views

Turing Machine Emulation in C++ Segmentation Fault [closed]

I am trying to create a Turing machine that accepts strings such as w#w. W is a binary string, and the machine accepts the strings that are equal to each other with a # between them. Im using pointers ...
Haider Muhammad's user avatar
0 votes
0 answers
8 views

Desing a turnig machine to find area of triangle if B and H given in Unary format

I want to implement the area of triangle in a turning machine i.e 1/2(b*h) Please tell me the format of the tape i mean how will the machine work in this scenerio i tried to combine the steps of mul. ...
Jay Patel's user avatar
0 votes
1 answer
43 views

Language for Turing Machine

Maybe someone can shine some light on this problem: When given the Language L which is defined as: L := {w ϵ {a,b}* : w=(aba | ba | (ba | w')), with w' ϵ L} What kind of word can this Language create? ...
Silver Ms's user avatar
0 votes
1 answer
60 views

Unable to export Chains class from Julia's Turing library

I am using Julia's Turing library to do the analysis using the MCMC method, and I am able to get the output of type Chains and store it in the variable chain. However, I am unable to write it out to a ...
Hinata235's user avatar
1 vote
0 answers
87 views

Complicated, long equations in MCMC [Julia, Turing.jl]

In my model I use several complicated functions (long equations, basically some polynomials) to evaluate my model. I want to perform efficient MCMC (NUTS) using Turing.jl. [For now data is only ...
RuBisCO's user avatar
  • 11
0 votes
0 answers
66 views

Turing Pattern Formation

this is a snipped code from page 261 of the textbook "Introduction to the modeling and analysis of complex system". I don't know why my visualized output wouldn't flow with time. import ...
weida's user avatar
  • 1
0 votes
0 answers
44 views

Is there a way to prove that the intersection of a decidable language and a recognizable language is also recognizable?

I’m unsure if this is true or false, I’m thinking that all strings in a recognizable language are decidable, so the only strings in the intersection would be decidable? I’m not sure how to formalize ...
stevo's user avatar
  • 1
0 votes
0 answers
23 views

binary search with JFLAP turing machine

A binary number is placed on the tape of a Turing machine (the input alphabet is {0, 1, □}). The head of the machine is positioned over the first element of the input. I need to write a program for ...
Alif Effendi's user avatar
0 votes
2 answers
41 views

python - 3 Turing Machine script, getting errors on an undefined variable, even though I assigned it

I'm working on a Turing machine in python and i'm getting an error for an undefined variable even though I have assigned it. Any help? the exact error is Traceback (most recent call last): File &...
Adrian Wheeler's user avatar
0 votes
0 answers
40 views

Prove that the following problem is undecidable by a reduction from the halting problem:

Prove that the following problem is undecidable by a reduction from the halting problem: “Does a given Turing Machine M accept any string of form a^2k for k ≥ 1?” I'm having trouble understanding the ...
Suleyman Kiani's user avatar
0 votes
1 answer
121 views

Construct a Turing Machine that halts on an unbroken string of 1s

So my homework is on Turing Machines and one of the questions that I've no idea how to start is: Design a TM that if given an unbroken string of 1s on an otherwise blank tape, will halt and the read/...
Sid's user avatar
  • 1
0 votes
0 answers
59 views

Jump to a specific vector place if a condition is met and start reading it from there

We need to create a universal Turing machine. We have a file with the provided information: tape count, starting input, starting position and the rules. Reading from the file isn't that big of a ...
righN's user avatar
  • 37
0 votes
0 answers
29 views

Decidability on Turing machine problems

I was studying some topics closely related to Turing machine where I came across a statement which said the following: A Turing machine M producing a Language having atleast k strings is undecidable, ...
h4kr's user avatar
  • 238
0 votes
0 answers
95 views

How to construct two-tape Turing Machine that decides a language with specific number of inputs

I am supposed to write a two-tape Turing machine (low level, all states, complete 7-tuple) to decide the following language: L = {w : w has exactly i a’s, exactly j b’s, and exactly k c’s, and k > ...
jamesvs642's user avatar
0 votes
0 answers
41 views

single and double sided infinite tapes turing machine

My question is do we have infinite null values at both end of the tape of a turing machine or we can have a single sided infinite nulls as well. Also if both of them are valid, do we have to make ANY ...
Moaz Haroon's user avatar
1 vote
1 answer
719 views

Binary to unary turing machine

How to implement a turing machine that converts the input from binary to unary? Example: given input-$101 The output should be -1^5=11111
user20989422's user avatar
1 vote
1 answer
192 views

How to generate an Unrestricted grammar if a language defination is given

How to construct unrestricted grammar that generates L = {a^ib^j c^k^d^l : i not equal to k AND j not equal to l}. a is to the power of i, 'b' raised to the power of j, 'c' raised to the power of k, '...
newman's user avatar
  • 21
1 vote
1 answer
75 views

Can we assure a strictly decreasing function is computable?

I've been assigned to solve an exercise that questions the following: Suppose a function f: N->N that is strictly decreasing. Can we assure f is computable? So far I've found that all non-...
Pol's user avatar
  • 13
0 votes
1 answer
66 views

Why is this Turing Machine not a decider?

Like I get that a Turing Machine is a decider if it halts for every input. But for this question, it just gave me this diagram and asked me to deduce whether this Turing Machine was considered a ...
Loren Beer's user avatar
0 votes
0 answers
10 views

How to demonstate that 2^F(x) is compile-time knowing that F(x) is a compile-time function

Sorry for my english. I don't know if I use the right terminology. DEF.: F is a compile-time function if exist the Turing machine which run-time doesn't depend on the input. I know that for the ...
TIzLibb's user avatar
1 vote
2 answers
75 views

Are there any functions that are computable but not curriable?

Sorry if I'm a bit lost. I've recently started learning about different programming language paradigms and I found that all texts presuppose that all functions written in a programming language are ...
David Velasco Pérez's user avatar
0 votes
0 answers
58 views

Input string: Exception in thread "main" java.util.NoSuchElementException: No line found at java.base/java.util.Scanner.nextLine(Scanner.java:1651)

Why am i getting this error Input string: Exception in thread "main" java.util.NoSuchElementException: No line foundat java.base/java.util.Scanner.nextLine(Scanner.java:1651)at TMSimulator....
Chris Ndirangu's user avatar
1 vote
1 answer
335 views

Why do we define equivalent turing machines as two turing machines with the same accepted languages?

From many textbooks about computability, I see how we define equivalent turing machines as follows: Two turing machines TM1 and TM2 are equivalent <=> L(TM1) = (TM2) where L(TM1) is the ...
Neil Zhang's user avatar
-1 votes
1 answer
206 views

What is the quickest algorithm to merge input symbols and remove blanks in a turing machine

I am looking to find an algorithm that would let me while starting at the right most of an input string containing blanks in between, merge input symbols so that there are no blanks. For example, 0 _ ...
Kieran Anderson's user avatar
1 vote
1 answer
446 views

Constructing a Turing Machine that deletes every second input symbol and then merges remaining string into a string with no blank gaps

Example input: 010101, output: 000 Example input: 10011, output: 101 Example input: 11101101, output: 1110 While drawing a state diagram for this problem, I am confused by how to merge the input ...
Kieran Anderson's user avatar
1 vote
1 answer
320 views

Turing machine |x-y|

The problem is not about programming, but about algorithm. We need to solve |x-y| in unary code on the Turing machine. For example if we have 111 * 11 on the tape. * as a number separator, then we ...
Mykola's user avatar
  • 25
-1 votes
1 answer
48 views

L={aʲbᵏaˡ | l = j * k} Context free? Recursive?

I have to classify the language L={aˆjbˆkaˆl | l = j * k}. I applied the pumping lemma for CFL and think that it is not context free. However, to prove that it is in fact recursive or recursively ...
nTn's user avatar
  • 9
0 votes
0 answers
78 views

How do you show that a language is in the class P, or Unknown?

I have two languages: L1 = { <G> | G is a graph that contained a n - 5 clique } L2 = { <G> | G is a graph that contained an Euler path } I need to figure out if these languages are in ...
Martian_mars's user avatar
-1 votes
1 answer
105 views

How to build special turing machine

Good day. I have a question. Many people are familiar with the Turing machine. The following task arose, which I can’t solve for a long time: there is an alphabet consisting of the letters "X&...
nyar's user avatar
  • 37
0 votes
0 answers
96 views

Understanding the primitives which Turing showed to be sufficient for a programming language

So it was said that Turing showed there are 6 primitives . i could think them as essentials needed to make programs. So the move left/right command makes sense because while writing code we might ...
Paracetamol's user avatar
2 votes
1 answer
125 views

Turing machine to solve a^(0+1+2+3+....+n)

Can anyone give me some insight how that Turing machine can be implemented? L = Xa^n n >= 0 and n = 0 + 1 + 2 + 3 +....+ M accepted examples: Xa ->(0+1) Xaaa -> (0+1+2) Xaaaaaa (...
Ugur Kellecioglu's user avatar
1 vote
0 answers
1k views

Turing machine for multiplication of two unary number

I am creating a Turing machine that computes the multiplication of two numbers using unary representation within 300 step limit. For example 2 * 3 as 110111 and output as 111111. and 3 * 5 as ...
HY2000's user avatar
  • 171
0 votes
1 answer
3k views

Design a turing machine to accept {1^n : n is prime number}

Design a Turing Machine to accept {1^n: n is prime number}. I have this homework to make a recognizer Turing Machine that will be accepted if the occurrences of 1 are equal to any prime number. As of ...
dullyourmind's user avatar
0 votes
1 answer
325 views

Is the following language decidable? L = {<M> : M(x) is a Turing machine with running time bounded by 100|x|^2 + 200}

L = {<M> : M(x) is a Turing machine with running time bounded by 100|x|^2 + 200} I think L is undecidable but I can't solve that. Please help me prove it. Thanks!
Wang's user avatar
  • 1
0 votes
1 answer
1k views

The difference between halting and accepting in a Turing machine

I use the textbook "an introduction to formal languages and automata", 6th edition by Peter Linz. In Definition 11.2, it seems that a Turing machine "M accepts language L" and &...
RyanKao's user avatar
  • 321
1 vote
0 answers
117 views

Multi-thread context switching in register-less machine

As I know, multi-thread context switching is pre-emptive initiated by the OS, transparent from the perspective of thread. Generally, when context switching, OS saves all the register values and ...
Sourav Kannantha B's user avatar
1 vote
0 answers
47 views

L_mult={a^i b^ij c^j:i,j≥0}, what would be the graph of diagram machine

L_mult={a^i b^ij c^j:i,j≥0}, what would be the diagram of turing machine. Here the number of b's will be equal to the number of a's times number of c's. How can draw the turning machine of this ...
kowser66's user avatar
  • 135
2 votes
1 answer
2k views

Context-sensitive Grammar for a^nb^nc^n

Is the following CSG for a^nb^nc^n correct? S->aSbC|abc Cb->bC C->c If not please explain why?
Preethi Y's user avatar
1 vote
1 answer
355 views

Find the Unrestricted Grammar for the language: L = {(a^i b^i)^j (c^k d^k)^j | i, j, k ≥ 1}

I'm having trouble determining a grammar for the L language. I've developed something that came close, but it's still not quite enough: S → XSY | Z X → aXb | ab Y → cYd | cd cZd → cd This grammar I ...
unknown's user avatar
  • 11
0 votes
0 answers
49 views

Why in max-cut ( weigthted graph )we can't do an approximation lower than 1/2?

I have been trying to solve the Max-Cut problem using approximation algorithms, but I still don't get how the best approximation I can get is 1/2. I could use any help or paper of proof of this fact.
feedback's user avatar
1 vote
0 answers
305 views

jflap duplicating states or transitions

I was wondering if there was a way we could "copy" and "paste" states/transitions in jflap? For example take the following one: Say I wanted to duplicate the transition from q1-&...
perrywinkle's user avatar
1 vote
0 answers
117 views

How would a Turing machine implement memory protection, interrupts, or real timer that a modern CPU has?

I understand that most of the modern CPU's are Turing complete (if given an infinite memory and time). From the below, I am going to assume that the amount of memory is infinite or as much sufficient ...
user13397022's user avatar
0 votes
2 answers
1k views

Prove that we can decide whether a Turing machine takes at least 100 steps on some input

We know that the problem “Does this Turing machine take at least this finite number of steps on that input?” is decidable, because it will always answer yes or no, where it will say yes if the machine ...
Ananya Nayak's user avatar
0 votes
1 answer
425 views

Why NP problem can not be solved using deterministic Turing machine, however every NTM has TM

Since every Non deterministic Turing machine has an equivalent deterministic Turing machine. Why we can not solve NP problem using the deterministic TM?
Ahmed_A's user avatar
  • 87
0 votes
0 answers
289 views

How to make a Turing machine which reads and writes 1s and 0s? C#

So i have a Homework task to create a Turing machine which uses a string like 101 and if it reads a 0 it writes 1 and if it reads a 1 it writes a 0. It uses a Transition rules with states. The full ...
adam hockney's user avatar
0 votes
1 answer
258 views

Recognizabilty of a set in regards to their size bounds

Trying to teach myself Computational Theory, and stumbled upon this question: Suppose we have two sets: {T | T is a turing machine and L(T) contains at least 1001 string} {T | T is a turing machine ...
DazedAndConfused's user avatar
0 votes
1 answer
614 views

Recursive vs recursively enumerable language in Turing Machines?

We say language L is recursive if it is decided by a TM. L is recursively enumerable (r.e.) if it's recognized by a TM. Suppose, enumerator (en-r) is a deterministic Turing Machine with a printer that ...
lee2020's user avatar
  • 15
0 votes
1 answer
457 views

operations on turing machine

Consider the problem: List := {< A, c> | A is a list of integers that contains a,b such that a + b = c} where the length of A is n. The algorithm we use to show that this problem is in class P ...
chris765's user avatar
0 votes
0 answers
223 views

Two head Turing Machine

I have this exercise Imagine a Turing Machine that has two heads and one tape. You need to: Give a clear explanation of computation for this type of TM. Include a formal description of computation. ...
Ene Andrei's user avatar
0 votes
0 answers
51 views

TOC program A that when given any program B as input can determine whether or not B produces “hello world”

“It is not possible to create a computer program A that when given any program B as input can determine whether or not B produces “hello world” as its first statement”.? need proof.
Sajjad Sarwar's user avatar

1
2 3 4 5
10