For each of the following decision problems, either sketch an algorithm or prove that the problem is undecidable. Recall that w denote the reversal of string w. For each problem, the input is an encoding (M, w) of a Turing machine M and its input string w. (a) Does M either accept w or reject wk? (b) If we run M on input w, does M ever change a symbol on its tape? (c) If we run M on input w, does M ever leave its start state? (d) If we run M on input w, does M ever reenter its start state?

For each of the following decision problems, either sketch an algorithm or prove that the problem is undecidable. Recall that w denote the reversal of string w. For each problem, the input is an encoding (M, w) of a Turing machine M and its input string w. (a) Does M either accept w or reject wk? (b) If we run M on input w, does M ever change a symbol on its tape? (c) If we run M on input w, does M ever leave its start state? (d) If we run M on input w, does M ever reenter its start state?

Computer Networking: A Top-Down Approach (7th Edition)

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

See similar textbooks

Similar questions

Consider the following language L over Σ = {0, 1, 2}: L = { 0i2 1 2 02i1i | i ≥ 0 } 1. Construct a Turing machine accepting L. Justify your answer, explaining how the TM youconstructed will accept words in the language L. 2. Give an accepting run of your TM for the word 0212001 Hint: think about the TM accepting the language { 0i2 1 2 02i1i | i ≥ 0 } and how can it be changed to accept the language above. Notation: recall that e.g. we write 0i for the word consisting of i-many 0’s.
Given the below nondeterministic Turing Machine: 1-Show the computation tree of the string acc 2-For the same string Show the values on the three tapes of a multi-tape deterministic Turing machine equivalent to the below Turing Machine. Show where is the location of the head on each tape at each time. Address the nodes in the computation from point 1 of this question, do not address the root node. a → a, R C → c, R a → a,R q3 q5 qo q1 c → c,L a → a, R 94 c → c, R
Give the transition diagram of a standard Turing Machine that implements the function. Briefly explain your solution strategies. DO NOT COPY YOUR ANSWER FROM CHEGG
Consider the problem of determining whether a state in a Turing machine is useless. Formulate this problem as a language, and show that it’s undecidable.
not handwritten Prove that the following problem is not decidable: Given a Turing Machine M, does the machine reject every input. (i.e., does L(M) = ∅)?
We are going to write a Turing machine that reads a string of 1's as input and produces a 1 for output if the string is a length that is a multiple of 3 and outputs a O otherwise. The 1 or O should be spaced 1 position to the right of the end of the input. You may assume that the input contains only zero or more 1's. For example here are four before and after snapshots. Before After B1 В Input is zero 1's (0 is a multiple of 3) <== 1 1 0 11 11 0 111 111 1 Here is a Turing machine that does most of the work but is missing one instruction. Fill the blank with the instruction needed. Follow the format of the other instructions (ie, current-state current- head head-instruction new-state, with exactly one space between each). qO 1 R q1 q1 1 R q2 q2 1 R q0 q0 BR q3 q1 BR q4 93 В 1 q5 q4 B0 q6 Hint: I suggest you draw what is given and then figure out what single instruction will make the machine behave as described.
Give the transition diagram of a standard Turing Machine that implements the function. Brie y explain your solution strategies.