The Turing Machine

[steve_bank]

https://en.wikipedia.org/wiki/Turing_machine

The Turubg Machune was a pre digital electronics general computational model. In computer sciEnce computation means algorithms, not numerical calculation.

Turing imagined an ifinite paper tape divided into cells. A read/write head could index the tape backwards and forwards, read a symbol, and write a symbol. The symbols are arbitrary. The read/write head executes an algorithm on the symbols, today we say software. Paper tape Teletype machines were in existence, probably where got the inspiration in part. A recipe for a cake is an algorithm.

It is stated without proof that for a problem to be solvable it must be Turing Computable. In Theory Of Computaion you start with logic trees and graphs, and get to the point where there a classes of problems that can not be solved with logic alone. Memoery is required. In CS it is called push down automata, in the modern processor a stack.

The modern processor is a Turing Machine without infinite memory. Symbols in the form of digital bits are written and read from memory. The TM tape head becomes the processor. The paper tape becomes sequential random access memory.

Turing created the modern computer model. He was hounded and jailed by the British govt for being gay even though he was key to the WWII code breaking team. He was given a posthumus pardon in the 90s I think.

 

[lpetrich]

Alan Turing proved some interesting theorems about Turing machines. For instance, a sufficiently capable Turing machine can emulate any other Turing machine ("Turing universality"). To map onto a sufficiently-capable Turing machine, a system must support the following:

1. Arbitrary array indexing
2. Arbitrary number of repeats of control-flow blocks. That is, no upper limit set before entering a control-flow block

In practice, the first one will be limited by resource limits, but that is usually ignored.

Most programming languages are Turing-complete. Turing-incomplete ones are not very common. The best-known ones are HTML, CSS, and SQL.

The cryptocurrency Bitcoin has a scripting language, but it is not used much. It is intentionally not Turing-complete, so that completion can be guaranteed (Script - Bitcoin Wiki).

Another cryptocurrency, Ethereum, has a Turing-complete scripting language, but it gets around the halting problem by enforcing a specified limit on how much scripting execution it will do.

 

[Phil Scott]

Alan Turing proved some interesting theorems about Turing machines. For instance, a sufficiently capable Turing machine can emulate any other Turing machine ("Turing universality"). To map onto a sufficiently-capable Turing machine, a system must support the following:

1. Arbitrary array indexing
2. Arbitrary number of repeats of control-flow blocks. That is, no upper limit set before entering a control-flow block

In practice, the first one will be limited by resource limits, but that is usually ignored.

Most programming languages are Turing-complete. Turing-incomplete ones are not very common. The best-known ones are HTML, CSS, and SQL.

The cryptocurrency Bitcoin has a scripting language, but it is not used much. It is intentionally not Turing-complete, so that completion can be guaranteed (Script - Bitcoin Wiki).

Another cryptocurrency, Ethereum, has a Turing-complete scripting language, but it gets around the halting problem by enforcing a specified limit on how much scripting execution it will do.

Technically, C isn't Turing complete. It has a fixed limit on the size of a word, and so a limit on the amount of memory available.

 

[steve_bank]

The physical processor is the physical TM.

You can build a TM in high level software, but it is translated down to the hard encoded processor commands.

C was unique at the time because it allowed indexing through memory by physical address. Pointers, which became problematic. C has a stack function, or push down automata. You can create it in any language. All you need is an array and code to push and pop off the array. LIFO, last in first out.

What I remember from Theory Of Computation class as an example a parser in a compiler can not parse imbedded parenthesis without a stack, IOW a TM.

 

[Phil Scott]

The physical processor is the physical TM.

You can build a TM in high level software, but it is translated down to the hard encoded processor commands.

C was unique at the time because it allowed indexing through memory by physical address. Pointers, which became problematic. C has a stack function, or push down automata. You can create it in any language. All you need is an array and code to push and pop off the array. LIFO, last in first out.

What I remember from Theory Of Computation class as an example a parser in a compiler can not parse imbedded parenthesis without a stack, IOW a TM.

Regular languages, the stuff you can recognise with a finite state automata, and the stuff you can recognise with a regular expression, cannot include arbitrary nestings of parentheses. The next languages up from that on the standard hierarchy are those that can be expressed as context free grammars, which are recognisable with push down automata and recursive transition networks. This is still significantly less powerful than a Turing Machine: any recognition done with a context free grammar is guaranteed to halt.

 

[lpetrich]

Technically, C isn't Turing complete. It has a fixed limit on the size of a word, and so a limit on the amount of memory available.

The same is true of any physically-feasible computing system. Every such system will be limited by the finiteness of its available resources.

 

[Phil Scott]

Technically, C isn't Turing complete. It has a fixed limit on the size of a word, and so a limit on the amount of memory available.

The same is true of any physically-feasible computing system. Every such system will be limited by the finiteness of its available resources.

Of course. Turing Machines aren't finitely realisable. However, languages can be Turing complete, and many languages are, such as Lisp. C isn't.

 

[steve_bank]

The real breakthough Turing made was envisioning a set of basic operations that could be used to sysnthesize higher functions.

The 6800 was circa 1980, As an 8 bit processor iy had a max of 256 operation codes. It is the first processor I leared.

The basix functions are loop, compare, and, or, shift, move from and to memory and a few others. The same basic operations are in the processor on your PC.

Any math function you do in a PC calculator reduce to a set of very simple core binary functions typified in the link. Exactly what Turing saw.A compiler takes a high level abstraction like a = b + c and traslates the expression to assembly language as in the link. An assembler converts operation codes tp bibary for loading into memory. The code column in the table is the hexadecimal for binary. It also assigns memory locations for the 3 variables a,b,c.

operational codes
http://www.8bit-era.cz/6800.html

For the die hard mathemeticians, the symbolic representaions of the op codes is in Backus Naur Form. Its been a while, it is comming back to me.
https://en.wikipedia.org/wiki/Backus–Naur_form

Assebly laanguage example.
http://www.8bit-era.cz/

 

[steve_bank]

The physical processor is the physical TM.

You can build a TM in high level software, but it is translated down to the hard encoded processor commands.

C was unique at the time because it allowed indexing through memory by physical address. Pointers, which became problematic. C has a stack function, or push down automata. You can create it in any language. All you need is an array and code to push and pop off the array. LIFO, last in first out.

What I remember from Theory Of Computation class as an example a parser in a compiler can not parse imbedded parenthesis without a stack, IOW a TM.

Regular languages, the stuff you can recognise with a finite state automata, and the stuff you can recognise with a regular expression, cannot include arbitrary nestings of parentheses. The next languages up from that on the standard hierarchy are those that can be expressed as context free grammars, which are recognisable with push down automata and recursive transition networks. This is still significantly less powerful than a Turing Machine: any recognition done with a context free grammar is guaranteed to halt.

I took a continuing ed course in the 90s Theory Of Computation. Like most in my generation circa 1980 we leaned computing from a few books and doing it. K&Rs C Programming Language was seminal. Knuth's Seminumerical Algoriothms.The class provided a good context.

As I rember it there are classes of problems that can not be solved without a TM.

 

[Bomb#20]

Alan Turing proved some interesting theorems about Turing machines. For instance, a sufficiently capable Turing machine can emulate any other Turing machine ("Turing universality"). To map onto a sufficiently-capable Turing machine, a system must support the following:

1. Arbitrary array indexing
2. Arbitrary number of repeats of control-flow blocks. That is, no upper limit set before entering a control-flow block

In practice, the first one will be limited by resource limits, but that is usually ignored.

Most programming languages are Turing-complete. Turing-incomplete ones are not very common. The best-known ones are HTML, CSS, and SQL.

The cryptocurrency Bitcoin has a scripting language, but it is not used much. It is intentionally not Turing-complete, so that completion can be guaranteed (Script - Bitcoin Wiki).

Another cryptocurrency, Ethereum, has a Turing-complete scripting language, but it gets around the halting problem by enforcing a specified limit on how much scripting execution it will do.

Number 1 is not necessary. Check out "Counter Machines". They're Turing-complete, even though they have no array indexing ability at all.

 

[steve_bank]

Alan Turing proved some interesting theorems about Turing machines. For instance, a sufficiently capable Turing machine can emulate any other Turing machine ("Turing universality"). To map onto a sufficiently-capable Turing machine, a system must support the following:

1. Arbitrary array indexing
2. Arbitrary number of repeats of control-flow blocks. That is, no upper limit set before entering a control-flow block

In practice, the first one will be limited by resource limits, but that is usually ignored.

Most programming languages are Turing-complete. Turing-incomplete ones are not very common. The best-known ones are HTML, CSS, and SQL.

The cryptocurrency Bitcoin has a scripting language, but it is not used much. It is intentionally not Turing-complete, so that completion can be guaranteed (Script - Bitcoin Wiki).

Another cryptocurrency, Ethereum, has a Turing-complete scripting language, but it gets around the halting problem by enforcing a specified limit on how much scripting execution it will do.

Number 1 is not necessary. Check out "Counter Machines". They're Turing-complete, even though they have no array indexing ability at all.

It sounds like in this case array and memory are synonymous.