6.8: Special Topic- What Can Be Computed?

Last updated
Save as PDF

Page ID: 58030

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Did you ever wonder whether there are problems that cannot be solved by a computer, no matter what kind of control structures are used? Well, back in 1939, in his seminal paper titled “On Computable Numbers,” Alan Turing proved that indeed there are an infinite number of unsolvable problems. Prior to this, mathematicians and logicians thought all problems could be solved. So Turing’s proof was quite a blow!

To help him prove this point, Turing defined an abstract computer, which has come to be known as a Turing machine. A Turing machine has an alphabet of symbols; a read/write head; an infinitely long tape on which the read/write head can write symbols, and from which it can also read symbols; and a control unit, which controls the movement and action of the read/write head. Note that the Turing machine elements correspond to key components of a real computer—although Turing invented this concept a decade before the first computers were developed. The read/write head corresponds to a computer’s central processing unit (CPU). The tape corresponds to the computer’s memory. And the control unit corresponds to the computer program.

A Turing machine represents a purely abstract concept of computation. It represents the pure idea of an algorithmic solution to a problem. Equipped with this concept, Turing was able to prove that there are unsolvable problems—that is, problems for which no algorithm can arrive at a solution.

One such problem is the halting problem. This problem asks whether an algorithm can be devised to determine whether an arbitrary program will eventually halt. If there were such an algorithm, it could be used to detect programs that contain infinite loops, a service that might be really helpful in an introductory computing lab, among other places! But, alas, there can be no such algorithm.

Here’s an outline of a proof that shows that the halting problem is unsolvable. (This particular version of the proof was suggested by J. Glenn Brookshear in Computer Science: An Overview, Benjamin-Cummings, 1985.)

Suppose you had a program, P, that solves the halting problem. That is, whenever P is given a self-halting program, it sets a variable isTerminating to true, and otherwise it sets isTerminating to false. Now let’s create a new version of P, named $P\prime$, which is identical to P except that right after where P sets isTerminating to true or false, $P\prime$ contains the following loop:

while (isTerminating == true);  // Infinite if isTerminating true

In other words, if the input to $P\prime$ is a self-terminating program, then $P\prime$ will enter an infinite loop and it won’t terminate. Otherwise, if a non-self-terminating program is input to $P\prime$, $P\prime$ will skip the loop and will terminate.

Now what if we give a representation of $P\prime$ to itself. Will it halt? The answer generates a contradiction: If $P\prime$ is a self-terminating program, then when it is input to itself, it will not terminate. And if $P\prime$ is not self-terminating, when it is input to itself, it will terminate. Because our assumption that P solves the halting problem has led to a contradiction, we have to conclude that it wasn’t a very good assumption in the first place. Therefore, there is no program that can solve the halting problem.

The topic of computability is a fundamental part of the computer science curriculum, usually taught in a sophomore- or junior-level theory of computation course.

conditional loop

counting loop

do-while statement

infinite loop

initializer

limit bound

loop body

loop bound

loop entry condition

nested loop

postcondition

precondition

priming read

repetition structure

sentinel bound

unit indexing

updater

while statement

zero indexing

A repetition structure is a control structure that allows a statement or sequence of statements to be repeated.

All loop structures involve three elements—an initializer, a loop entry condition or a loop boundary condition, and an updater.

When designing a loop, it is important to analyze the loop structure to make sure that the loop bound will eventually be satisfied.

The for statement has the following syntax:

for(initializer;loopentrycondition;updater)
forloopbody;

The while statement takes the following form:

while(loopentrycondition)
loopbody;

The do-while statement has the following general form:

do
loopbody;
while(loopentrycondition);

When designing a loop, it is important to analyze the loop structure to make sure that the loop bound will eventually be satisified. Table 6.2 summarizes the types of loop bounds that we have identified.

Structured programming is the practice of writing programs that are built up from a small set of predefined control structures—the sequence, selection, repetition, and method-call structures. An important feature of these structures is that each has a single entry and exit.

A precondition is a condition that must be true before a certain code segment executes. A postcondition is a condition that must be true when a certain code segment is finished. Preconditions and postconditions should be used in the design, coding, documentation, and debugging of algorithms and methods.

Identify the syntax error in the following for loop statements:

Commas are used instead of semicolons in the header.

 for (int k = 5; k < 100; k++)
     System.out.println(k);

There shouldn’t be 3 semicolons in the header

 for (int k = 0; k < 12 ; k--)
     System.out.println(k);

Identify those statements that result in infinite loops:

Infinite loop because k is never incremented.
Infinite loop because k is always odd and thus never equal to 100.

Your sister is learning to count by fours. Write a for loop that prints the following sequence of numbers: 1, 5, 9, 13, 17, 21, 25.

for (int k = 1; k <= 25; k = k+4)
    System.out.print(k + " ");

What value will j have when the following loop terminates? Answer: j will be undefined when the loop terminates. It is a local variable whose scope is limited to the loop body.

for (int i = 0; i < 10; i++)
{
   int j;
   j = j + 1;
}

Write a nested for loop to print the following geometric pattern:

#
# #
# # #
# # # #
# # # # #

for (int row = 1; row <= 5; row++)  {    // For each row
  for (int col = 1; col <= row; col++) // Columns per row
    System.out.print('#');
  System.out.println();                // New line
} // row

Identify the syntax error in the following while structures:

int k = 5;
while (k < 100) {
    System.out.println(k);
    k++                     << Missing semicolon
}

int k = 0;
while (k < 12;) {           << Extra semicolon
    System.out.println(k);
    k++;
}

Determine the output and/or identify the error in each of the following while structures.

int k = 0;
while (k < 100)
  System.out.println(k);  << Missing updater in loop body

Output: infinite loop prints 0 0 0 0 0...

while (k < 100) {           << Missing initializer
  System.out.println(k);
  k++;
}

Output: unpredictable since k’s initial value is not known

Your younger sister is now learning how to count by sixes. Write a while loop that prints the following sequence of numbers: 0, 6, 12, 18, 24, 30, 36.

   int k = 0;                 // Initializer
   while (k <= 36) {          // Loop-entry condition
       System.out.println(k);
       k += 6;                  // Updater
   }

If N is even, divide it by 2. If N is odd, subtract 1 and then divide it by 2. This will generate a sequence that is guaranteed to terminate at 0. For example, if N is initially 15, then you get the sequence 15, 7, 3, 1, 0. Write a method that implements this sequence using a while statement.

public static void sub1Div2(int N) {
    while(N != 0) {
        System.out.print(N + " ");
        if (N % 2 == 0)
            N = N / 2;
        else
            N = (N - 1) / 2;
    }
    System.out.println( N );
} // sub1Div2()

Identify the syntax error in the following do-while structures:

int k = 0;
do while (k < 100) << Misplaced condition
{
     System.out.println(k);
     k++;
}                    << Belongs here

int k = 0;
do {
    System.out.println(k);
    k++;
} while (k < 12) << Missing semicolon

Your sister has moved on to counting by sevens. Write a do-while loop that prints the following sequence of numbers: 1, 8, 15, 22, 29, 36, 43.

n = 1;                           // Initializer
do {
    System.out.print(n + " ");
    n += 7;                      // Updater
} while (n <= 43);                // Loop entry condition

Write a method to input and validate pizza sales.

public int getAndValidatePizzaPrice() {// Uses KeyboardReader
  int pizza = 0;
  do {
    reader.prompt("Input a pizza price (8, 10, or 15) ");
    reader.prompt("or 99 to end the list >> ");
    pizza = reader.getKeyboardInteger();
    if ((pizza != 99) && (pizza != 8) && (pizza != 10) && 
                       (pizza != 15))
      System.out.println("Error: you've entered an "
       + "invalid pizza price\n");    // Error input
    else                               // OK input
        System.out.println("You input " + pizza + "\n");                 
  } while ((pizza != 99) && (pizza != 8) && 
                   (pizza != 10) && (pizza != 15));
  return pizza;
} // getAndValidatePizzaPrice()

Write a method to input and validate pizza sales using the numbers 1, 2, and 3 to represent pizzas at different price levels.

public int getAndValidatePizzaPrice() { // Uses KeyboardReader
  int pizza = 0;
  do {
    reader.prompt("Input a 1,2 or 3 to indicate pizza" 
              + "price ( 1($8), 2($10), or 3($15) ) ");
    reader.prompt("or 0 to end the list >> ");
    pizza = reader.getKeyboardInteger();
    if ((pizza < 0) || (pizza > 3))  // Error check
        System.out.println("Error: you've entered an " 
                                + "invalid value\n");  
    else                                // OK input
        System.out.println("You input " + pizza + "\n"); 
  } while ( (pizza < 0) || (pizza > 3) );
  if (pizza == 1)
    return 8;
  else if (pizza == 2)
    return 10;
  else if (pizza == 3)
    return 15;
  else
    return 0;
} // getAndValidatePizzaPrice()

For each of the following problems, decide whether a counting loop structure, a while structure, or a do-while structure should be used, and write a pseudocode algorithm.

Printing the names of all the visitors to a Web site could use a counting loop because the exact number of visitors is known.

for each name in the visitor's log
    print the name

Validating that a user has entered a positive number requires a do-while structure in which you repeatedly read a number and validate it.

do
    read a number
    if number is invalid, print error message
while number is invalid

Changing all the backslashes ($\backslash$) in a Windows Web page address, to the slashes (/) used in a Unix Web page address.

for each character in the Web page address
    if it is a backslash replace it with slash

Finding the largest in a list of numbers requires a while loop to guard against an empty list.

initialize maxMPG to smallest possible number
while there are more cars in the database
    if current car's MPG is greater than maxMPG
        replace maxMPG with it

Identify any errors in the following switch structures (if there is no error, specify the output):

   int k = 0;
   switch (k)  // Syntax error: missing braces
   case 0:
       System.out.println("zero");
       break;
   case 1:
       System.out.println("one");
       break;
   default:
       System.out.println("default");
       break;

   int k = 0;
   switch (k + 1) 
   {   
       case 0:
           System.out.println("zero");
           break;
       case 1:
           System.out.println("one"); // Output "one"
           break;
       default:
           System.out.println("default");
           break;
   }

   int k = 6;
   switch (k / 3.0) // Syntax error: not an integral value
   {   
       case 2:
           System.out.println("zero");
           break;
       case 3:
           System.out.println("one");
           break;
       default:
           System.out.println("default");
           break;
   }

A switch statement to print ice cream flavors:

switch (flavor) 
{   
    case 1:
        System.out.println("Vanilla");
        break;
    case 2:
        System.out.println("Chocolate");
        break;
    case 3:
        System.out.println("Strawberry");
        break;
    default:
        System.out.println("Error");
}

public final int VANILLA = 0,
                 CHOCOLATE = 1,
                 STRAWBERRY = 2;
switch (flavor) 
{   
    case VANILLA:
        System.out.println("Vanilla");
        break;
    case CHOCOLATE:
        System.out.println("Chocolate");
        break;
    case STRAWBERRY:
        System.out.println("Strawberry");
        break;
    default:
        System.out.println("Error");
}

Identify the pre- and postconditions on j and k where indicated in the following code segment:

int j = 0; k = 5;
do {
    if (k % 5 == 0) {
                      // Precondition: j <= k
        j += k;
        k--;
    }
    else k *= k;
} while (j <= k);
                      // Postcondition: j > k

Identify the pre- and postconditions for the following method, which computes $x^n$ for $n >= 0$.

 // Precondition: N >= 0
 // Postcondition: power(x,n) == x to the n
 public double power(double x, int n ) {
     double pow = 1;
     for (int k = 1; k <= n; k++)
         pow = pow * x;
     return pow;
 } // power()

Explain the difference between the following pairs of terms:

Counting loop and conditional loop.

For statement and while statement.

While statement and do-while statement.

Zero indexing and unit indexing.

Sentinel bound and limit bound.

Counting bound and flag bound.

Loop initializer and updater.

Named constant and literal.

Compound statement and null statement.

Fill in the blank.

=14pt

The process of reading a data item before entering a loop is known as a

A loop that does nothing except iterate is an example of

A loop that contains no body is an example of a

statement.

A loop whose entry condition is stated as $( k < 100\; ||\; k >= 0)$ would be an example of an

loop.

A loop that should iterate until the user types in a special value should use a

bound.

A loop that should iterate until its variable goes from 5 to 100 should use a

bound.

A loop that should iterate until the difference between two values is less than 0.005 is an example of a

bound.

=11pt

Identify the syntax errors in each of the following:

for (int k = 0; k < 100; k++) System.out.println(k)

for (int k = 0; k < 100; k++); System.out.println(k);

int k = 0 while k < 100 System.out.println(k); k++;

int k = 0; do System.out.println(k); k++; while k < 100 ;

Determine the output and/or identify the error in each of the following code segments:

for (int k = 1; k == 100; k += 2) System.out.println(k);

int k = 0; while (k < 100) System.out.println(k); k++;

for (int k = 0; k < 100; k++) ; System.out.println(k);

Write pseudocode algorithms for the following activities, paying particular attention to the initializer, updater, and boundary condition in each case.

a softball game

a five-question quiz

looking up a name in the phone book

Identify the pre- and postconditions for each of the statements that follow. Assume that all variables are int and have been properly declared.

int result = x / y;

int result = x

int x = 95; do x /= 2; while(x >= 0);

Write three different loops—a for loop, a while loop, and a do-while loop—to print all the multiples of 10, including 0, up to and including 1,000.

Write three different loops—a for loop, a while loop, and a do-while loop—to print the following sequence of numbers: 45, 36, 27, 18, 9, 0, $-9$, $-18$, $-27$, $-36$, $-45$.

Write three different loops—a for loop, a while loop, and a do-while loop—to print the following ski-jump design:

#
# #
# # #
# # # #
# # # # #
# # # # # #
# # # # # # #

The Straight Downhill Ski Lodge in Gravel Crest, Vermont, gets lots of college students on breaks. The lodge likes to keep track of repeat visitors. Straight Downhill’s database includes an integer variable, visit, which gives the number of times a guest has stayed at the lodge (1 or more). Write the pseudocode to catch those visitors who have stayed at the lodge at least twice and to send them a special promotional package (pseudocode = send promo). (Note: The largest number of stays recorded is eight. The number nine is used as an end-of-data flag.)

Modify your pseudocode in the previous exercise. In addition to every guest who has stayed at least twice at the lodge receiving a promotional package, any guest with three or more stays should also get a $40 coupon good for lodging, lifts, or food.

Write a method that is passed a single parameter, N, and displays all the even numbers from 1 to N.

Write a method that is passed a single parameter, N, that prints all the odd numbers from 1 to N.

Write a method that is passed a single parameter, N, that prints all the numbers divisible by 10 from N down to 1.

Write a method that is passed two parameters—a char Ch and an int N—and prints a string of N Chs.

Write a method that uses a nested for loop to print the following multiplication table:

   1  2  3  4  5  6  7  8  9
1  1
2  2  4
3  3  6  9
4  4  8 12 16
5  5 10 15 20 25
6  6 12 18 24 30 36
7  7 14 21 28 35 42 48
8  8 16 24 32 40 48 56 64
9  9 18 27 36 45 54 63 72 81

Write a method that uses nested for loops to print the patterns that follow. Your method should use the following statement to print the patterns: System.out.print('#').

# # # # # # # #     # # # # # # # #   # # # # # # # #   # # # # # # # #
  # # # # # # #     # # # # # # #       #         #                 #
    # # # # # #     # # # # # #           #     #                 #
      # # # # #     # # # # #               # #                 #
        # # # #     # # # #                 # #               #
          # # #     # # #                 #     #           #
            # #     # #                 #         #       #
              #     #                 # # # # # # # #   # # # # # # # #

Write a program that asks the user for the number of rows and the number of columns in a box of asterisks. Then use nested loops to generate the box.

Write a Java application that lets the user input a sequence of consecutive numbers. In other words, the program should let the user keep entering numbers as long as the current number is one greater than the previous number.

Write a Java application that lets the user input a sequence of integers terminated by any negative value. The program should then report the largest and smallest values that were entered.

How many guesses does it take to guess a secret number between 1 and N? For example, I’m thinking of a number between 1 and 100. I’ll tell you whether your guess is too high or too low. Obviously, an intelligent first guess would be 50. If that’s too low, an intelligent second guess would be 75. And so on. If we continue to divide the range in half, we’ll eventually get down to one number. Because you can divide 100 seven times (50, 25, 12, 6, 3, 1, 0), it will take at most seven guesses to guess a number between 1 and 100. Write a Java Swing program that lets the user input a positive integer, N, and then reports how many guesses it would take to guess a number between 1 and N.

Suppose you determine that the fire extinguisher in your kitchen loses X percent of its foam every day. How long before it drops below a certain threshold (Y percent), at which point it is no longer serviceable? Write a Java Swing program that lets the user input the values X and Y and then reports how many weeks the fire extinguisher will last.

Leibnitz’s method for computing $\pi$ is based on the following convergent series:

\[\frac{\pi}{4} \; = 1 \; - \; \frac{1}{3} \; + \; \frac{1}{5} \; - \; \frac{1}{7} + \; \cdots\]

How many iterations does it take to compute $\pi$ to a value between 3.141 and 3.142 using this series? Write a Java program to find out.

Newton’s method for calculating the square root of N starts by making a (nonzero) guess at the square root. It then uses the original guess to calculate a new guess, according to the following formula:

guess = (( N / guess) + guess) / 2;

No matter how wild the original guess is, if we repeat this calculation, the algorithm will eventually find the square root. Write a square root method based on this algorithm. Then write a program to determine how many guesses are required to find the square roots of different numbers. Uses Math.sqrt() to determine when to terminate the guessing.

Your employer is developing encryption software and wants you to develop a Java Swing Program that will display all of the primes less than N, where N is a number to be entered by the user. In addition to displaying the primes themselves, provide a count of how many there are.

Your little sister asks you to help her with her multiplication and you decide to write a Java application that tests her skills. The program will let her input a starting number, such as 5. It will generate multiplication problems ranging from from $5 \times 1$ to $5 \times 12$. For each problem she will be prompted to enter the correct answer. The program should check her answer and should not let her advance to the next question until the correct answer is given to the current question.

Write an application that prompts the user for four values and draws corresponding bar graphs using an ASCII character. For example, if the user entered 15, 12, 9, and 4, the program would draw

******************
************
*********
****

Revise the application in the previous problem so that the bar charts are displayed vertically. For example, if the user inputs 5, 2, 3, and 4, the program should display

 **
 **       **
 **    ** **
 ** ** ** **
 ** ** ** **
-------------

The Fibonacci sequence (named after the Italian mathematician Leonardo of Pisa, ca. 1200) consists of the numbers $0,1,1,2,3,5,8,13,\dots$ in which each number (except for the first two) is the sum of the two preceding numbers. Write a method fibonacci(N) that prints the first N Fibonacci numbers.

The Nuclear Regulatory Agency wants you to write a program that will help determine how long certain radioactive substances will take to decay. The program should let the user input two values: a string giving the substance’s name and its half-life in years. (A substance’s half-life is the number of years required for the disintegration of half of its atoms.) The program should report how many years it will take before there is less than 2 percent of the original number of atoms remaining.

Modify the CarLoan program so that it calculates a user’s car payments for loans of different interest rates and different loan periods. Let the user input the amount of the loan. Have the program output a table of monthly payment schedules.