Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #37605

Re: Thorough Mathematical intro to "computer 'science'" ...

Show key headers only | View raw

On Fri, 27 Oct 2017 10:37:33 -0400, Arne Vajhøj wrote:

> On 10/27/2017 3:33 AM, Joerg Meier wrote:
>> On 24 Oct 2017 04:02:10 GMT, Stefan Ram wrote:
>>> =?UTF-8?Q?Albretch_M=c3=bcller?= <tekmonk2005@yahoo.com> writes:
>>>> Hmm! What is it exactly you can't implement with a computer?
>>>    (Obviously, one cannot write a Java program that will read another
>>>    Java program and output whether the other Java program will
>>>    terminate. But I was not thinking about this.)
>> 
>> Excuse me ? Are you seriously claiming that Java is not Turing
>> complete, or did I misunderstand your statement ?
> 
> https://en.wikipedia.org/wiki/Halting_problem
> 
> <quote>
> Alan Turing proved in 1936 that a general algorithm to solve the halting
> problem for all possible program-input pairs cannot exist. A key part of
> the proof was a mathematical definition of a computer and program, which
> became known as a Turing machine; the halting problem is undecidable
> over Turing machines. It is one of the first examples of a decision
> problem.
> </quote>
> 
> https://en.wikipedia.org/wiki/Turing_completeness
> 
> <quote>
> In computability theory, a system of data-manipulation rules (such as a
> computer's instruction set, a programming language, or a cellular
> automaton) is said to be Turing complete or computationally universal if
> it can be used to simulate any Turing machine. The concept is named
> after English mathematician and computer scientist Alan Turing.
> </quote>
> 
> Stefan's statement seems to match fine as far as I can see.
> 
> Arne
>
Yep. I've seen descriptions of Turing machines and one description of a 
hardware implementation. Interesting stuff. 

The implementation, described in A.K. Dewdney's book "The Armchair 
Universe" the the 'Busy Beavers' chapter was based on a 6809 chip with a 
'memory'capable of holding 4096 marks.

However, just about all of the more abstract descriptions have assumed 
that the program was a Finite State Machine implementation.

Sorry if this is off topic, but although I have no intention of building 
or implementing a Turing Machine, I do find them fascinating. Maybe its a 
side effect of living reasonably close to Bletchley Park and having seen 
the rebuilt Bombe sitting there, dripping oil and the reconstructed 
Colossus fired up and running.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Thorough Mathematical intro to "computer 'science'" ... Albretch Müller <tekmonk2005@yahoo.com> - 2017-10-22 19:28 -0400
  Re: Thorough Mathematical intro to "computer 'science'" ... Albretch Müller <tekmonk2005@yahoo.com> - 2017-10-23 14:49 -0400
    Re: Thorough Mathematical intro to "computer 'science'" ... Joerg Meier <joergmmeier@arcor.de> - 2017-10-27 09:33 +0200
      Re: Thorough Mathematical intro to "computer 'science'" ... Arne Vajhøj <arne@vajhoej.dk> - 2017-10-27 10:37 -0400
        Re: Thorough Mathematical intro to "computer 'science'" ... Martin Gregorie <martin@address-in-sig.invalid> - 2017-10-29 01:40 +0000
      Re: Thorough Mathematical intro to "computer 'science'" ... Martin Gregorie <martin@address-in-sig.invalid> - 2017-10-27 17:25 +0000
        Re: Thorough Mathematical intro to "computer 'science'" ... Joerg Meier <joergmmeier@arcor.de> - 2017-10-28 23:30 +0200

csiph-web