Tail recursion to while iteration in 2 easy steps

[Ravi Sahni]

The mathematical ideal Turing Machine has an infinitely long tape,
equivalent to infinite memory, and may take an unbounded amount of time
to complete the computation. Since no *actual* physical machine can be
infinitely big, and in practice there are strict limits on how long we
are willing to wait for a computation to complete, in the *literal*
sense, Turing Machines are not *actual* machines. They are a mathematical
abstraction.

But in practice, we can wave our hands and ignore this fact, and consider
only not-quite-Turing Machines with finite amounts of tape, and note that
they are equivalent to physical machines with finite amounts of memory.
One could even build such a finite Turing Machine, although of course it
would be very slow. Or one can simulate it in software.

So in that sense, computers are Turing Machines. Anything a physical
computing device can compute, a Turing Machine could too. The converse is
not true though: a Turing Machine with infinite tape can compute things
where a real physical device would run out of memory, although it might
take longer than anyone is willing to wait.

Thanks Sir the detailed explanation. You are offering me many thoughts
inside few words so I will need some time to meditate upon the same.

Presently Sir, I wish to ask single question: What you mean "wave our hands"??

Thanks

 

[Ravi Sahni]

To explain at length will be too long and OT (off-topic) for this list.
I'll just give you a link and you tell me what you make of it:
http://sloan.stanford.edu/mousesite/Secondary/Whorfframe2.html

I am trying to read link. Very new idea: Buildings can catch fire by
wrong boards!!

Later part difficult for me to read. (My English not powerful --please excuse.)
I will make my fullest efforts to read on your recommend but I not
clear the connection with computers, programming, computer science and
so on. Also this Mr. Mark Lawrence question.

 

[Steven D'Aprano]

Thanks Sir the detailed explanation. You are offering me many thoughts
inside few words so I will need some time to meditate upon the same.

Presently Sir, I wish to ask single question: What you mean "wave our
hands"??

It is an idiom very common in Australia. (It may not be well known in the
rest of the English-speaking world.) It means to figuratively flap one's
hands around in the air while skipping over technical details or
complications. For example, we often talk about "hand-wavy estimates" for
how long a job will take: "my hand-wavy estimate is it will take two
days" is little better than a guess.

 

[rusi]

I am trying to read link. Very new idea: Buildings can catch fire by
wrong boards!!

Later part difficult for me to read. (My English not powerful --please excuse.)
I will make my fullest efforts to read on your recommend

Hell No! I only asked you to read the first page!

but I not
clear the connection with computers, programming, computer science and
so on. Also this Mr. Mark Lawrence question.

Once you get that buildings can catch fire by wrong terminology you should get that:
- the term 'Turing machine' can make people think its a machine even thoughits a mathematical formalism
- the term 'λ-calculus' (partly due to the word calculus and partly due to the greek lambda) makes people think its mathematics even though its acomputational framework

 

[Mark Janssen]

I don't have an infinite stack to implement

And then


Having it both ways aren't you?

I'm just speaking from programmer experience and the fact that most
machines are VonNeumann architecture. Being that as it is, maxing out
the stack simply happens, and I don't dare do any non-simple
recursion, but otherwise, practically speaking, I can calculate my
memory usage that may grow on the heap so that is effectively a
non-issue. This may not be an important distinction for computing,
the "art" (Hello ultimate lambda friends), but it is significant for
the computing, the science.

MarkJ
Tacoma, Washington

 

[Chris Angelico]

It is an idiom very common in Australia. (It may not be well known in the
rest of the English-speaking world.) It means to figuratively flap one's
hands around in the air while skipping over technical details or
complications. For example, we often talk about "hand-wavy estimates" for
how long a job will take: "my hand-wavy estimate is it will take two
days" is little better than a guess.

A derivative of the term has gone mainstream, too:

http://tvtropes.org/pmwiki/pmwiki.php/Main/HandWave

The term is commonly used when moving to a higher level of abstraction
- we all know a computer doesn't have a soul, can't "feel", and is
ultimately just executing code and crunching numbers, but we handwave
that (eg) the computer "thought" that this program was a risk, and
that's why it quarantined it. When you're trying to explain to some
user that he can't email .EXE files around, it's easier to take the
slightly-inaccurate but simple explanation, hence the handwaves.

ChrisA

 

[Charles Hixson]

It's not mistaken.

I'm afraid it is. Reality trumps your theory. gcc, clang, Microsoft
Visual Studio, and all the many, many other C compilers do not generate
identical machine code even when targeting the same hardware. This is a
fact. It's not even the case that there is One True Way to implement a
particular program on a given hardware device and compilers merely are
buggy for doing something else. There are often different ways to
implement it which are equally good, the only difference being personal
preference.

Given a stable and formalized language definition,
there should only be continued optimization of the lexical and
procedural constructs into better machine code.

Better than what? "Continued" optimization? When you say "lexical and
procedural constructs", do you mean "source code"?

In the case of an
"interpreted" language like Python (which I'll define as a language
which includes a layer of indirection between the user and the machine,

Irrelevant. In the case of Python, there is a machine. The fact that it
is a VM rather than a physical machine is irrelevant. A machine is a
machine -- we could be talking about a Lisp Machine, a Forth Machine, a
x86 processor, an Motorola 68000, an Atom processor, one of those old
Russian mainframes that used three-state trits instead of two-state bits,
or even Babbage's Analytical Engine.

Besides, most modern CPUs don't execute machine code directly, they run
the machine code in a virtual machine implemented in hardware. So the
difference between Python and x86 machine code is just a matter of degree.

encouraging the nice benefits of interactivity), such optimization isn't
really apropos, because it's not the purpose of python to be optimal to
the machine as much as "optimal to the programmer". In any case, while
such optimization can continue over time, they generally create new
compiler releases to indicate such changes. The one-to-one mapping is
held by the compiler.

Such determinism *defines* the machine, otherwise you might as well get
rid of the notion of computer *science*. All else is error, akin to
cosmic rays or magic. Unless the source code changes, all else
remaining equal, the machine code is supposed to be the same, no matter
how many times it is compiled.

That is akin to saying that there is *only one* way to measure the speed
of light (say), standing in exactly the same place, using exactly the
same equipment, using precisely the same measurement techniques, and that
if we allow alternative methods for measuring the speed of light, physics
is no longer a science.

[Only if you use the exact source, compiler, switches, etc]] will the
output be the same.
And even that is not guaranteed.

Oh, and what would cause such non-determinism?

The compiler-writer, of course. A compiler is software, and is written by
a person, who can program it to do anything the writer wants. If the
writer wants the compiler to be non-deterministic, it can be.

Some viruses use a similar technique to try to avoid virus scanners. They
encrypt the payload, which is functionally equivalent to randomizing it
(except it can be reversed if you have the key) so as to defeat virus
scanners.

A more whimsical example: perhaps a mischievous compiler writer included
something like this in her compiler:


when compiling integer multiplication, INT * INT:
if today is Tuesday:
emit machine code that does multiplication using repeated addition
otherwise:
emit machine code that does multiplication using ADD and SHIFT


Both implementations of multiplication are perfectly valid. There may be
a performance difference, or there may not be. Since no sensible
programming language is going to specify the *detailed* machine code
implementation of its high-level operations, such a mischievous compiler
would still be valid.

Well, since you didn't specify your programming language, you're then
merely stating an English construct.

What difference does it make? But if it will make you feel better, I'm
specifying Hypertalk. You've probably never heard of it, but regardless,
it exists, and it has a sort command, and the high-level language does
not specify which of many sort algorithms is to be used.

As such, there can be no single
mapping from English into the machine, which is why there are so many
different languages and experiments that map your [English] concepts
into source code.

And there is no single mapping from <INSERT **ANY** HIGH-LEVEL
PROGRAMMING LANGUAGE HERE> source code to machine code either.

I would assert that Python is not inherently a virtual machine
language. Originally, IIRC, it was believed that LISP couldn't be
compiled. Also, you could implement that virtual machine as a hardware
machine. (Also, of course, on modern hardware assembly language is run
on a virtual machine, implemented by an underneath microcode layer.)

You can reasonably say that an implementation of Python is done in terms
of a virtual machine. (Usually I don't bother about this kind of
nit-pick, but in this discussion it seems apropos.)