From: fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON)
Newsgroups: alt.folklore.computers,alt.religion.computers
Subject: Re: Good source code to read?

lowen@lorc.UUCP (Lamar Owen) writes:
>I'm not a Computer Science student; I'm an engineer who happens to hack a 
>little (I used to do lots of hacks, but I no longer can take the time...).  So,
>although I've been following this thread, I want to know two things: 
>
>1.) What, exactly, IS a Turing Machine (Note that I have an idea what one is,
>    I just don't know the *rigoroous* CS definition)?

Basically, a Turing machine is a machine with an infinite length tape,
a tape read/write head, and a finite number of states.
Each execution consists of reading the tape symbol under the read/write head,
and then determining on the basis of that symbol and the current state whether
to halt, and if not, which symbol to write and which direction (left or right)
to move the tape read/write head in.

More formally,

A Turing machine is a sextuple (Q, Epsilon, Gamma, B, delta, q0) where
	Q is a finite set of states
	Gamma is a finite set, called the tape alphabet
	B is an element of Gamma, called the blank symbol
	Epsilon is a subset of Gamma - {B} called the input alphabet
	delta is a partial function from Q * Gamma to Q * Gamma * 2
		called the transition function
	q0 is an element of Q, called the start symbol

There are also a lot of variants, eg. two-way tape, n-track machine, n-tape
machine, nondeterministic.

>2.) What is the Halting Problem?  From the articles in this thread thus far, I
>    have a pretty good idea.

Given any Turing machine, and given the initial contents of the tape
(the input must be finite - the rest of the tape will be blank),
determine whether or not the computation will halt.

>3.) (I lied)  Why is this Halting Problem so important?????

(a) We would like to be able to prove that our programs are correct.
    One prerequisite for this is to at least prove that our programs
    halt for a given input. (Some programs are not supposed to halt,
    but most programs are... we would like to be able to prove that those
    in the latter category DO eventually halt for all input.

(b) A lot of other problems can be shown to be undecideable by reducing them
    to the halting problem.

-- 
Fergus Henderson             fjh@munta.cs.mu.OZ.AU      


From: duening@ibr.cs.tu-bs.de (Lars Duening)
Newsgroups: alt.folklore.computers,alt.religion.computers
Subject: Re: Good source code to read?

fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON) write:
> lowen@lorc.UUCP (Lamar Owen) writes:
>> I'm not a Computer Science student; I'm an engineer who happens to hack a 
>> little (I used to do lots of hacks, but I no longer can take the time...).
>> So, although I've been following this thread, I want to know two things: 
>>
>>1.) What, exactly, IS a Turing Machine (Note that I have an idea what one is,
>>    I just don't know the *rigoroous* CS definition)?
> 
> Basically, a Turing machine is a machine with an infinite length tape,
> a tape read/write head, and a finite number of states.
> Each execution consists of reading the tape symbol under the read/write head,
> and then determining on the basis of that symbol and the current state 
> whether to halt, and if not, which symbol to write and which direction (left
> or right) to move the tape read/write head in.
> 
> [more formal definition deleted]
> 
> There are also a lot of variants, eg. two-way tape, n-track machine, n-tape
> machine, nondeterministic.

I'd like to add that the importance of turing machines come from two facts:
first it's possible to build Universal Turing Machines which are capable
to emulate every other Turing Machine (even themselves), and second, up to
today nobody found proof that modern computers aren't just sophisticated
turing machines.

And that's why the Halting Problem has such an importance.

Lars Duening; Am Wendenwehr 25  |  EMail: duening@ibr.cs.tu-bs.de
D-W3300 Braunschweig; Germany   |  Voice: +49-351-345693