Question 10. Consider the function defined by f(n) = 2n where n is a positive integer....
Question 10. Consider the function defined by f(n) = 2n where n is a positive integer.
(i) Can this function be computed by a Turing machine? Why or why not? (
ii) Is this function primitive recursive? Why or why not?
Homework Answers
1. The function can be computed by a turing machine as it can be computed by a modern computer. Since a turing machine can simulate ANY computer algorithm, it can simulate the above function as well.
2. A function that can be implemented using only do-loops is called primitive recursive. The function can be written using loop and running it 2 times adding the value of n to a sum varibale initialised to 0. Hence it is a primitive recursive function.
Hope this helped. Please do upvote and if there are any queries please ask in comments section.
Add Answer to:
Question 10. Consider the function defined by f(n) = 2n where n
is a positive integer....
Consider the function defined by f(n) = 2 nwhere n is a positive integer. (i) Can...
Consider the function defined by f(n) = 2 nwhere n is a positive integer. (i) Can this function be computed by a Turing machine? Why or why not? (ii) Is this function primitive recursive? Why or why not?
Question 9. Consider the language {a"b" : n >0}. (i) Is this a regular language? Why...
Question 9. Consider the language {a"b" : n >0}. (i) Is this a regular language? Why or why not? (ii) Is this a recursively enumerable language? Why or why not? Question 10. Consider the function defined by f(n) = 2 where n is a positive integer. (i) Can this function be computed by a Turing machine? Why or why not? (ii) Is this function primitive recursive? Why or why not?
Consider Fibonacci number F(N), where N is a positive integer, defined as follows. F(1) = 1...
Consider Fibonacci number F(N), where N is a positive integer, defined as follows. F(1) = 1 F(2) = 1 F(N) = F(N-1) + F(N-2) for N > 2 a) Write a recursive function that computes Fibonacci number for a given integer N≥ 1. b) Prove the following theorem using induction: F(N) < ΦN for integer N≥ 1, where Φ = (1+√5)/2.
Question 6 of 19 Python The factorial of a positive integer n, fact(n), is defined recursively...
Question 6 of 19 Python The factorial of a positive integer n, fact(n), is defined recursively as follows: fact(n) 51, when n51 fact(n) 5n * fact(n21), otherwise Define a recursive function fact that returns the factorial of a given positive integer.
Fix an integer N>1, and consider the function f:[0,1]R defined as follows: if XE[0,1] and there...
Fix an integer N>1, and consider the function f:[0,1]R defined as follows: if XE[0,1] and there is an integer n with 1<n<N such that nxez, choose n with this property as small as possible, and set f(x) := 1/n^2; otherwise set f(x):=0. Show that f is 0 integrable, and S f.
Prove using mathematical induction that for every positive integer n, = 1/i(i+1) = n/n+1. 2) Suppose...
Prove using mathematical induction that for every positive integer n, = 1/i(i+1) = n/n+1. 2) Suppose r is a real number other than 1. Prove using mathematical induction that for every nonnegative integer n, = 1-r^n+1/1-r. 3) Prove using mathematical induction that for every nonnegative integer n, 1 + i+i! = (n+1)!. 4) Prove using mathematical induction that for every integer n>4, n!>2^n. 5) Prove using mathematical induction that for every positive integer n, 7 + 5 + 3 +.......
Third time posting, can someone answer please. Question 2. Consider the Turing machine defined as follows....
Third time posting, can someone answer
please.
Question 2. Consider the Turing machine defined as follows. input alphabet {1} Tape alphabet = { 1,0, x,□} where □ represents a blank Set of states (A, B, C, D Initial state A set of accept states = {D} Transition function: 6(A, z) = (A,z, R) 6(A, □)-(C,D, L) (i) Draw a transition graph for this Turing machine. (ii) Determine the output of the Turing machine for each of the following input i)...
3 For each positive integer n, define E(n) 2+4++2n (a) Give a recursive definition for E(n)....
3 For each positive integer n, define E(n) 2+4++2n (a) Give a recursive definition for E(n). (b) Let P(n) be the statement E(n) nn1)." Complete the steps below to give a proof by induction that P(n) holds for every neZ+ i. Verify P(1) is true. (This is the base step.) ii. Let k be some positive integer. We assume P(k) is true. What exactly are we assuming is true? (This is the inductive hypothesis.) iii. What is the statement P(k...
Consider the sequence defined as a[1] = 2; and a[k] = a[k-1]+2*k-1 for all positive integer...
Consider the sequence defined as a[1] = 2; and a[k] = a[k-1]+2*k-1 for all positive integer k >= 2; . Show that a[n] = 1+sum(2*i-1, i = 1 .. n); . Hint: Start with sum(2*i-1, i = 1 .. n);and use the recursive definition of the sequence.
1 Fix an integer N > 1, and consider the function f : [0,1] - R...
1 Fix an integer N > 1, and consider the function f : [0,1] - R defined as follows: if 2 € (0,1) and there is an integer n with 1 <n<N such that nx € Z, choose n with this property as small as possible, and set f(x) := otherwise set f(x):= 0. Show that f is integrable, and compute Sf. (Hint: a problem from Homework Set 7 may be very useful for 0 this!)
Question 9. Consider the language {a"b" : n >0}. (i) Is this a regular language? Why or why not? (ii) Is this a recursively enumerable language? Why or why not? Question 10. Consider the function defined by f(n) = 2 where n is a positive integer. (i) Can this function be computed by a Turing machine? Why or why not? (ii) Is this function primitive recursive? Why or why not?
Fix an integer N>1, and consider the function f:[0,1]R defined as follows: if XE[0,1] and there is an integer n with 1<n<N such that nxez, choose n with this property as small as possible, and set f(x) := 1/n^2; otherwise set f(x):=0. Show that f is 0 integrable, and S f.
Prove using mathematical induction that for every positive integer n, = 1/i(i+1) = n/n+1. 2) Suppose r is a real number other than 1. Prove using mathematical induction that for every nonnegative integer n, = 1-r^n+1/1-r. 3) Prove using mathematical induction that for every nonnegative integer n, 1 + i+i! = (n+1)!. 4) Prove using mathematical induction that for every integer n>4, n!>2^n. 5) Prove using mathematical induction that for every positive integer n, 7 + 5 + 3 +.......
Third time posting, can someone answer
please.
Question 2. Consider the Turing machine defined as follows. input alphabet {1} Tape alphabet = { 1,0, x,□} where □ represents a blank Set of states (A, B, C, D Initial state A set of accept states = {D} Transition function: 6(A, z) = (A,z, R) 6(A, □)-(C,D, L) (i) Draw a transition graph for this Turing machine. (ii) Determine the output of the Turing machine for each of the following input i)...
3 For each positive integer n, define E(n) 2+4++2n (a) Give a recursive definition for E(n). (b) Let P(n) be the statement E(n) nn1)." Complete the steps below to give a proof by induction that P(n) holds for every neZ+ i. Verify P(1) is true. (This is the base step.) ii. Let k be some positive integer. We assume P(k) is true. What exactly are we assuming is true? (This is the inductive hypothesis.) iii. What is the statement P(k...
1 Fix an integer N > 1, and consider the function f : [0,1] - R defined as follows: if 2 € (0,1) and there is an integer n with 1 <n<N such that nx € Z, choose n with this property as small as possible, and set f(x) := otherwise set f(x):= 0. Show that f is integrable, and compute Sf. (Hint: a problem from Homework Set 7 may be very useful for 0 this!)
Most questions answered within 3 hours.
-
Computer Programming II CS141(Java)
Mention the appropriate relationship between following
classes:
HOD–StaffMember
Car–Ferrari
Student-Address
BankAccount–FixedAccount
House-Building...
asked 2 hours ago -
Assume one of your finals has 50 questions on it, and
lucky for you, it's all...
asked 3 hours ago -
Rice Products in Bangladesh
Business behavior is derived in large part from the basic cultural
environment...
asked 5 hours ago -
The following base sequence is found for a mRNA fragment from
wild-type E. coli: 5'- UAUCAGUAGAUAAUGUAACC-3'...
asked 5 hours ago -
For this exercise, round all regression parameters to three
decimal places.
One of the two tables...
asked 5 hours ago -
What is the 5% level of significance for mean = 3.60, standard
deviation = 0.94, and...
asked 5 hours ago -
Prior to beginning work on this discussion, please read the
article by Hayley Peterson, 15 Companies...
asked 6 hours ago -
Which pair of aqueous solutions, when mixed, will form a
precipitate?
A) NaNO3 and AgC2H3O2
B)...
asked 6 hours ago -
1-Write an algorithm to get two numbers from the user (as
inputs) and calculate the sum...
asked 9 hours ago -
Define white-collar crime. What is the difference between
offender and offense-based definitions of white-collar crime? What...
asked 10 hours ago -
Consider a reaction which is 1st order with respect to A and 1st
order with respect...
asked 10 hours ago -
c++
The length of the hypotenuse of a right-angled triangle is the
square root of the...
asked 10 hours ago