1. Forum
  2. Usenet
  3. COMP.UNIX.SHELL

  • Is bash a Turing-complete language and how to validate this by a minima

    From [email protected]@21:1/5 to All on Wed Aug 16 17:58:49 2023
    Hi here,

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

    Regards,
    Zhao

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Kaz Kylheku@21:1/5 to [email protected] on Thu Aug 17 01:25:26 2023
    On 2023-08-17, [email protected] <[email protected]> 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: @[email protected]

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Janis Papanagnou@21:1/5 to [email protected] on Thu Aug 17 05:48:10 2023
    On 17.08.2023 02:58, [email protected] 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


    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Rick Hohensee@21:1/5 to [email protected] on Sat Aug 26 06:45:43 2023
    On Wednesday, August 16, 2023 at 8:58:57 PM UTC-4, [email protected] 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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Kaz Kylheku@21:1/5 to Rick Hohensee on Sat Aug 26 18:47:53 2023
    On 2023-08-26, Rick Hohensee <[email protected]> wrote:
    On Wednesday, August 16, 2023 at 8:58:57 PM UTC-4, [email protected] 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: @[email protected]

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)