Unsolvable Problem

Jack Dikian

October 1999

The Halting Problem is one of the simplest problems known to be unsolvable. Given a program and an input to the program (input-program pair), determine if the program will eventually stop when it is given that input.

Turing pondered if there was a way of telling in general once a computer has embarked on a calculation whether that calculation will terminate in an answer. This problem is known as the "Halting Problem for Turing Machines" and was first proved in the 1937 paper in which he described his machines.

My interest in this was caught when writing a Turing Machine simulator and was fascinated by the seemingly simple challenge – and Turing’s elegant solution.

Introduction

Briefly, a Turing machine can be thought of as a black box, which performs a calculation of some kind on an input number. If the calculation reaches a conclusion, or halts then an output number is returned. Otherwise, the machine theoretically just carries on forever. The problem is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will run forever.

There are an infinite number of Turing machines, as there are an infinite number of calculations that can be done with a finite list of rules. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. We say that the halting problem is undecidable over Turing machines.

Break here

Download author's Turing Machine simulator and article "Halting Problem Made Simple, October 1999"

Apparatus For Removing Hidden Lines from Bezier Surfaces

Jack Dikian

November 2000

This paper describes the work carried out by the author in implementing an apparatus for removing hidden lines from Bezier surfaces on the Tektronix storage tube technology of the early 80’s.

Bézier surface

A Bézier surface is formed as the cartesian product of the blending functions of two orthogonal Bézier curves. Bézier surfaces, first described in the early 60’s by the French engineer Pierre Bézier and used in automobile body design.

Hidden lines

When rendering a three dimensional surface on a two dimensional plane such as a computer screen, lines which should otherwise not seen by the viewer must be removed. The shape of the surface, if opaque, should not be cluttered by overlapping lines. Importantly, our real world experience does not allow for us to “see” through what is a solid surface or object.

In order to remove these lines, hidden line algorithms are applied in the surface rendering software to create a wire-frame which contains only visible lines and hides the lines covered by the surface.

There are a number of algorithms used to remove hidden lines. Arthur Appel’s work at IBM in the late 1960’s for example works by propagating the visibility from a segment with a known visibility to a segment whose visibility is yet to be determined. By a comparison of the two following images, the line removal algorithm can be seen at work as the wireframe representation of the surface shaded object removes the lines which are not in view.

Whilst much of the initial work in hidden line removal was done by Arthur Appel, the field is still growing as there are exceptions when his algorithm is not effective. There is a variety of other algorithms which are implemented in computer-assisted design such as the object-precision algorithms of Weiss and Galimberti/Montenari and the image-precision algorithms Encarnacao (priority-edge intersection test and scan grid – point/surface test), Warnock, and Watkins.

The Approach