### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# THEORY OF COMPUTATION CSCE 551

GPA 3.61

### View Full Document

## 31

## 0

## Popular in Course

## Popular in Computer Science and Engineering

This 9 page Class Notes was uploaded by Trace Mante MD on Monday October 26, 2015. The Class Notes belongs to CSCE 551 at University of South Carolina - Columbia taught by M. Alekseyev in Fall. Since its upload, it has received 31 views. For similar materials see /class/229570/csce-551-university-of-south-carolina-columbia in Computer Science and Engineering at University of South Carolina - Columbia.

## Reviews for THEORY OF COMPUTATION

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/26/15

Theory of Computation Lecture 11 Algorithms Max Alekseyev University of South Carolina February 19 2009 Algorithms Algorithms have been around since ancient times lnformally they can be called procedures or recipies One of the famous algorithms was given by Euclid around 300 BC now called Euclid39s algorithm for finding the greatest common divisor GCD of two integers However there was no rigorous definition of the algorithm until the twentieth century Hilbert s Tenth Problem In 1900 at the International Congress of Mathematicians David Hilbert posed a list of open problems as a challenge for the coming century The tenth problem problem was about an algorithm He asked to devise a procedure for answering to the question whether a given polynomial such as 6X3yz2 i 3xy2 7 X3 7 10 possess an integer root ie a set of integer values of the varibles at which the polynomial takes zero value eg X 5 y 3 z O is an integer root of the above polynomial Hilbert s Tenth Problem In 1900 at the International Congress of Mathematicians David Hilbert posed a list of open problems as a challenge for the coming century The tenth problem problem was about an algorithm He asked to devise a procedure for answering to the question whether a given polynomial such as 6X3yz2 l 3xy2 7 X3 7 10 possess an integer root ie a set of integer values of the varibles at which the polynomial takes zero value eg X 5 y 3 z O is an integer root of the above polynomial By asking to devise a procedural way to answer this question Hilbert implicitly assumed that such a procedure algorithm exists However as was proved 70 years later by Yuri Matijasevic there no such algorithm exists There was no way to come up with this conclusion without the definition of algorithm Church Tu ring thesis The definition of the algorithm came in the 1936 papers of Alonzo Church and Alan Turing Their definitions using calculus and Turing machines respectively turned out to be equivalent Since then the connection between the informal notion of an algorithm and the precise definition is called the Church Turing thesis Church Tu ring thesis The definition of the algorithm came in the 1936 papers of Alonzo Church and Alan Turing Their definitions using calculus and Turing machines respectively turned out to be equivalent Since then the connection between the informal notion of an algorithm and the precise definition is called the Church Turing thesis Hilbert39s Tenth Problem basically asks to construct a decider for the language D p l p is a polynomial with an integer root That is for any given polynomial p we need to decide whether p E D in a finite number of steps Example Finding an integer root A Turing machine for finding a integer root of a given polynomial of a single varible X for simplicity can be informally described as gt Evaluate a given polynomial pX at X set successively to the values 07177172772737737 gt If at any such value of X the value pX is zero then accept Q Is this Turing machine recognizer or decider Example Finding an integer root A Turing machine for finding a integer root of a given polynomial of a single varible X for simplicity can be informally described as gt Evaluate a given polynomial pX at X set successively to the values 07177172772737737 gt If at any such value of X the value pX is zero then accept Q Is this Turing machine recognizer or decider For a univariate polynomial it is possible to compute an upper bound for an absolute value of its integer root If no root found below this bound the polinomial has no integer roots and its TM can reject making it a decider solving the problem However as shown by Matijasevic for multivariate polynomials no such bound can be computed making it impossible to have a decider for this problem in general case Description of Algorith ms Algorithms can be described in three ways formal Explicit description of a Turing machine its states transition function etc implementation Description of TM using English prose ie how TM moves head readwrites symbols etc without explicitly specifying its states and transition function high level Description of an algorithm using English prose ignoring implementation details We start with the first two levels and later will switch to the third one when you feel confident on how to go from one level of algorithm description to another

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.