1 Which of the following is TRUE? Universal Turing Machines are made out of silicon. Universal Turing Machines can implement the procedures and follow the instructions of any Turing machine. Universal Turing Machines provide a method for proving any true mathematical theorem. Universal Turing Machines can compute functions that no other Turing machined can compute. 2 Turing says the question "Can a machine think?" is too vague and proposes that we replace this question with which of the following? Can a machine speak a language? Can a machine fool someone into thinking it is male or female? Can a machine fool someone into thinking it is alive? Can a machine successfully play the "imitation game"?

1 Which of the following is TRUE? Universal Turing Machines are made out of silicon. Universal Turing Machines can implement the procedures and follow the instructions of any Turing machine. Universal Turing Machines provide a method for proving any true mathematical theorem. Universal Turing Machines can compute functions that no other Turing machined can compute. 2 Turing says the question "Can a machine think?" is too vague and proposes that we replace this question with which of the following? Can a machine speak a language? Can a machine fool someone into thinking it is male or female? Can a machine fool someone into thinking it is alive? Can a machine successfully play the "imitation game"?

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

a) Create a Turing Machine that accepts if the first integer is higher than the second and rejects otherwise. b) Create a multi-tape Turing Machine.
2) Recall that a final state of a Turing machine T is a state that is not the first state in any of the 5-tuples that make up T. Construct a Turing machine that recognizes the set {0²n1n | n ≥ 0}. Write down 5- tuples for the Turing Machine. (You will not receive credit if you only draw an FSM.)
Create a Turing machine for the following language: On Σ = {0,1} Language 1 (L1) every string in the language begin and end with 1 Language 2 (L2) all strings in the language begin with 001. The union of L1 and L2
) Build a Turing Machine over the alphabet Σ = {a,b} that accepts all words which do not start andend with the same letter. Show the execution traces with the following input strings:(a) Λ(b) abba(c) baba
1. Design a Turing machine that accepts the language L(aaaa*b*), where Σ = (a, b). 2. Design a Turing machine that accepts the complement of the language of the previous question. 3. Design a Turing machine with three states that accepts the language L(a (a+b)*).
If P≠NP, can the computational decision problems that can be solved by a nondeterministic turing machine, but not by a regular Turing machine exist? Explain.
INTRODUCTION TO THE THEORY OF COMPUTATION For each of the following languages: • Give an algorithm for a Turing Machine. • Produce a Turing Machine that corresponds to that algorithm 101m0n1m|n, m≥ 1}
Let L be a language. Explain, in your own words, how would you prove that: (a) L is regular, (b) Lis not regular, (c) L is context-free, (d) L is not context-free, (e) L is decidable, (f) L is notdecidable (undecidable), (g) L is Turing-recognizable, (h) L is not Turing-recognizable, (i) L isco-Turing-recognizable, (j) L is not co-Turing-recognizable.Also, give an example of each of these types of languages
Construct a Turing machine that computes the function ? of ? is equal to two ?, i.e. if the input is zero to the power ? then the output would be zero to the power two ? e.g. if it says 000 on the tape before the machine is run it should read 000000 on the tape when it has stopped.
4. Give a formal state diagram of a Turing Machine which recognizes the language {#a" + am : n+m = a' : n, m E N}. (You can use the "#" symbol to recognize the beginning of the tape.) SOLUTION:
6. Give the state diagram for a Turing machine that decides each of the following language over E = {0, 1}: a) L6= {w:w contains both the substrings 011 and 101} b) L7= {w:w contains at least two 0's and at most two 1's}
QUESTIONS Q1. Design a Turing Machine that calculates the following function: f(n,m)= [(n+m)/2] where [] means ceiling/the next integer above the result (for example, if the real result of division is 3.3 or 3.5 or 3.8 and such, the output of the function is 4). n21 and m21 is also given. Initial configuration: 0000...0011111...111AA..... n zeros m ones Final configuration: ΧΧXΧ .ΧΧXXXΧ .ΧΧ2222..2ΔΔ... n+m X's f(n,m) a) Explain how your machine works. b) Draw the state transition diagram of your machine. c) Give the execution chain for f(3,4).