Rocksolid Light

Welcome to Rocksolid Light

mail  files  register  newsreader  groups  login

Message-ID:  

We have phasers, I vote we blast 'em! -- Bailey, "The Corbomite Maneuver", stardate 1514.2

devel / comp.unix.shell / Re: Is bash a Turing-complete language and how to validate this by a minimal example?

SubjectAuthor
* Is bash a Turing-complete language and how to validate this by ahongy...@gmail.com
+- Is bash a Turing-complete language and how to validate this byKaz Kylheku
+- Is bash a Turing-complete language and how to validate this by aJanis Papanagnou
`* Is bash a Turing-complete language and how to validate this by aRick Hohensee
 `- Is bash a Turing-complete language and how to validate this byKaz Kylheku

1
Is bash a Turing-complete language and how to validate this by a minimal example?

<a2076c08-a29c-4347-ab92-930d018a58d2n@googlegroups.com>

  copy mid

https://news.novabbs.org/devel/article-flat.php?id=6562&group=comp.unix.shell#6562

  copy link   Newsgroups: comp.unix.shell
X-Received: by 2002:a1c:4c11:0:b0:3fc:21:2c42 with SMTP id z17-20020a1c4c11000000b003fc00212c42mr35739wmf.1.1692233931270;
Wed, 16 Aug 2023 17:58:51 -0700 (PDT)
X-Received: by 2002:a63:3642:0:b0:564:3bb7:b5a2 with SMTP id
d63-20020a633642000000b005643bb7b5a2mr357430pga.0.1692233930387; Wed, 16 Aug
2023 17:58:50 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.128.87.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.unix.shell
Date: Wed, 16 Aug 2023 17:58:49 -0700 (PDT)
Injection-Info: google-groups.googlegroups.com; posting-host=208.86.32.27; posting-account=kF0ZaAoAAACPbiK5gldhAyX5qTd3krV2
NNTP-Posting-Host: 208.86.32.27
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <a2076c08-a29c-4347-ab92-930d018a58d2n@googlegroups.com>
Subject: Is bash a Turing-complete language and how to validate this by a
minimal example?
From: hongyi.zhao@gmail.com (hongy...@gmail.com)
Injection-Date: Thu, 17 Aug 2023 00:58:51 +0000
Content-Type: text/plain; charset="UTF-8"
 by: hongy...@gmail.com - Thu, 17 Aug 2023 00:58 UTC

Hi here,

Is bash a Turing-complete language, and if so, how to validate this by a minimal example?

Regards,
Zhao

Re: Is bash a Turing-complete language and how to validate this by a minimal example?

<20230816180433.919@kylheku.com>

  copy mid

https://news.novabbs.org/devel/article-flat.php?id=6563&group=comp.unix.shell#6563

  copy link   Newsgroups: comp.unix.shell
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: 864-117-4973@kylheku.com (Kaz Kylheku)
Newsgroups: comp.unix.shell
Subject: Re: Is bash a Turing-complete language and how to validate this by
a minimal example?
Date: Thu, 17 Aug 2023 01:25:26 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 30
Message-ID: <20230816180433.919@kylheku.com>
References: <a2076c08-a29c-4347-ab92-930d018a58d2n@googlegroups.com>
Injection-Date: Thu, 17 Aug 2023 01:25:26 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="1aa1e972d16a2b9e389dd8d4860af990";
logging-data="3685380"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/zojE+fi8lAX0RqSPqWmz5XXNITOdfjBw="
User-Agent: slrn/1.0.3 (Linux)
Cancel-Lock: sha1:RcI6R2KOzZzd92pPxkyyQOzWFoU=
 by: Kaz Kylheku - Thu, 17 Aug 2023 01:25 UTC

On 2023-08-17, hongy...@gmail.com <hongyi.zhao@gmail.com> wrote:
> Hi here,
>
> Is bash a Turing-complete language, and if so, how to validate this by a minimal example?

The algorithmic subset of Bash: functions, variables, loops and all
that, isn't Turing complete because Turing completeness requires
unlimited storage. Bash is a C program bound in a bounded memory model.

However, files could be used as "tapes".

If a language A can interpret language B which is known to be Turing
complete, then A is Turing complete.

If you can write a Bash program which interprets Turing machine
tapes, using files, then you could argue that it's Turing complete,
limited only by the file size.

File size is limited only by the type of file system used.

Say that we hook up an actual tape machine to Linux, and write a driver
for it, and map it to a file-like device. We could have it so that the
Bash script uses this device, and is limited only by the amount of tape;
the operator can always splice on more tape if it looks like the tape is
running out.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

Re: Is bash a Turing-complete language and how to validate this by a minimal example?

<ubk59r$3l4gs$1@dont-email.me>

  copy mid

https://news.novabbs.org/devel/article-flat.php?id=6564&group=comp.unix.shell#6564

  copy link   Newsgroups: comp.unix.shell
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: janis_papanagnou+ng@hotmail.com (Janis Papanagnou)
Newsgroups: comp.unix.shell
Subject: Re: Is bash a Turing-complete language and how to validate this by a
minimal example?
Date: Thu, 17 Aug 2023 05:48:10 +0200
Organization: A noiseless patient Spider
Lines: 21
Message-ID: <ubk59r$3l4gs$1@dont-email.me>
References: <a2076c08-a29c-4347-ab92-930d018a58d2n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 17 Aug 2023 03:48:11 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="35648cce75d18029cc7e431451ca3345";
logging-data="3838492"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+3vAJndKydbBQbJnX2B6Kh"
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.8.0
Cancel-Lock: sha1:SSCLsVp9YeGt/56zBK6WTFYsE3I=
In-Reply-To: <a2076c08-a29c-4347-ab92-930d018a58d2n@googlegroups.com>
 by: Janis Papanagnou - Thu, 17 Aug 2023 03:48 UTC

On 17.08.2023 02:58, hongy...@gmail.com wrote:
> Hi here,
>
> Is bash a Turing-complete language, and if so, how to validate this by a minimal example?

The answer can be found in the Net; Wikipedia for example says:

"To show that something is Turing-complete, it is enough to show
that it can be used to simulate some Turing-complete system. No
physical system can have infinite memory, but if the limitation
of finite memory is ignored, most programming languages are
otherwise Turing-complete."

Janis

>
> Regards,
> Zhao
>

Re: Is bash a Turing-complete language and how to validate this by a minimal example?

<e362e925-4d0c-4592-849e-da53257703d3n@googlegroups.com>

  copy mid

https://news.novabbs.org/devel/article-flat.php?id=6583&group=comp.unix.shell#6583

  copy link   Newsgroups: comp.unix.shell
X-Received: by 2002:a05:6214:3905:b0:63c:edce:c71e with SMTP id nh5-20020a056214390500b0063cedcec71emr703327qvb.3.1693057543462;
Sat, 26 Aug 2023 06:45:43 -0700 (PDT)
X-Received: by 2002:a05:6808:1598:b0:3a4:24bc:125f with SMTP id
t24-20020a056808159800b003a424bc125fmr560020oiw.1.1693057543209; Sat, 26 Aug
2023 06:45:43 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!newsfeed.hasname.com!usenet.blueworldhosting.com!diablo1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.unix.shell
Date: Sat, 26 Aug 2023 06:45:43 -0700 (PDT)
In-Reply-To: <a2076c08-a29c-4347-ab92-930d018a58d2n@googlegroups.com>
Injection-Info: google-groups.googlegroups.com; posting-host=98.231.178.227; posting-account=OcRAMAoAAAArFDHhZFYw2-58_dk-x0_f
NNTP-Posting-Host: 98.231.178.227
References: <a2076c08-a29c-4347-ab92-930d018a58d2n@googlegroups.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <e362e925-4d0c-4592-849e-da53257703d3n@googlegroups.com>
Subject: Re: Is bash a Turing-complete language and how to validate this by a
minimal example?
From: presidentbyamendment@gmail.com (Rick Hohensee)
Injection-Date: Sat, 26 Aug 2023 13:45:43 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 1629
 by: Rick Hohensee - Sat, 26 Aug 2023 13:45 UTC

On Wednesday, August 16, 2023 at 8:58:57 PM UTC-4, hongy...@gmail.com wrote:
> Hi here,
>
> Is bash a Turing-complete language, and if so, how to validate this by a minimal example?
>
> Regards,
> Zhao
bash can't input binary data. C strings can't contain a 0. See my use of od to get around that in my subsequent post last night about Bit Banging Bash

Re: Is bash a Turing-complete language and how to validate this by a minimal example?

<20230826114702.123@kylheku.com>

  copy mid

https://news.novabbs.org/devel/article-flat.php?id=6585&group=comp.unix.shell#6585

  copy link   Newsgroups: comp.unix.shell
Path: i2pn2.org!i2pn.org!eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: 864-117-4973@kylheku.com (Kaz Kylheku)
Newsgroups: comp.unix.shell
Subject: Re: Is bash a Turing-complete language and how to validate this by
a minimal example?
Date: Sat, 26 Aug 2023 18:47:53 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 18
Message-ID: <20230826114702.123@kylheku.com>
References: <a2076c08-a29c-4347-ab92-930d018a58d2n@googlegroups.com>
<e362e925-4d0c-4592-849e-da53257703d3n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 26 Aug 2023 18:47:53 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="6a4d567afeb64b3fd2b1436d7ec348e3";
logging-data="768693"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19ioipt8azUXxxyZHUQiFAa3qEEXCyJCJs="
User-Agent: slrn/pre1.0.4-9 (Linux)
Cancel-Lock: sha1:N4uKbdKZM4VPHtKOTqmpzAJRZ/Q=
 by: Kaz Kylheku - Sat, 26 Aug 2023 18:47 UTC

On 2023-08-26, Rick Hohensee <presidentbyamendment@gmail.com> wrote:
> On Wednesday, August 16, 2023 at 8:58:57 PM UTC-4, hongy...@gmail.com wrote:
>> Hi here,
>>
>> Is bash a Turing-complete language, and if so, how to validate this by a minimal example?
>>
>> Regards,
>> Zhao
> bash can't input binary data.

What specific symbols are processed by the machine that's neither here
nor there with regard to Turing completeness.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor